<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-pragma">{-# LANGUAGE BangPatterns #-}</span><span>
</span><span id="line-2"></span><span>
</span><span id="line-3"></span><span class="hs-pragma">{-# OPTIONS_HADDOCK not-home #-}</span><span>
</span><span id="line-4"></span><span>
</span><span id="line-5"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-6"></span><span class="hs-comment">--</span><span>
</span><span id="line-7"></span><span class="hs-comment">-- = WARNING</span><span>
</span><span id="line-8"></span><span class="hs-comment">--</span><span>
</span><span id="line-9"></span><span class="hs-comment">-- This module is considered __internal__.</span><span>
</span><span id="line-10"></span><span class="hs-comment">--</span><span>
</span><span id="line-11"></span><span class="hs-comment">-- The Package Versioning Policy __does not apply__.</span><span>
</span><span id="line-12"></span><span class="hs-comment">--</span><span>
</span><span id="line-13"></span><span class="hs-comment">-- The contents of this module may change __in any way whatsoever__</span><span>
</span><span id="line-14"></span><span class="hs-comment">-- and __without any warning__ between minor versions of this package.</span><span>
</span><span id="line-15"></span><span class="hs-comment">--</span><span>
</span><span id="line-16"></span><span class="hs-comment">-- Authors importing this module are expected to track development</span><span>
</span><span id="line-17"></span><span class="hs-comment">-- closely.</span><span>
</span><span id="line-18"></span><span class="hs-comment">--</span><span>
</span><span id="line-19"></span><span class="hs-comment">-- = Description</span><span>
</span><span id="line-20"></span><span class="hs-comment">--</span><span>
</span><span id="line-21"></span><span class="hs-comment">-- This module provides the various sorting implementations for</span><span>
</span><span id="line-22"></span><span class="hs-comment">-- &quot;Data.Sequence&quot;. Further notes are available in the file sorting.md</span><span>
</span><span id="line-23"></span><span class="hs-comment">-- (in this directory).</span><span>
</span><span id="line-24"></span><span>
</span><span id="line-25"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Data.Sequence.Internal.Sorting</span><span>
</span><span id="line-26"></span><span>  </span><span class="hs-special">(</span><span>
</span><span id="line-27"></span><span>   </span><span class="annot"><span class="hs-comment">-- * Sort Functions</span></span><span>
</span><span id="line-28"></span><span>   </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sort"><span class="hs-identifier">sort</span></a></span><span>
</span><span id="line-29"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sortBy"><span class="hs-identifier">sortBy</span></a></span><span>
</span><span id="line-30"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sortOn"><span class="hs-identifier">sortOn</span></a></span><span>
</span><span id="line-31"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSort"><span class="hs-identifier">unstableSort</span></a></span><span>
</span><span id="line-32"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSortBy"><span class="hs-identifier">unstableSortBy</span></a></span><span>
</span><span id="line-33"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSortOn"><span class="hs-identifier">unstableSortOn</span></a></span><span>
</span><span id="line-34"></span><span>  </span><span class="hs-special">,</span><span>
</span><span id="line-35"></span><span>   </span><span class="annot"><span class="hs-comment">-- * Heaps</span></span><span>
</span><span id="line-36"></span><span>   </span><span class="annot"><span class="hs-comment">-- $heaps</span></span><span>
</span><span id="line-37"></span><span>   </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier">Queue</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-38"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QList"><span class="hs-identifier">QList</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-39"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier">IndexedQueue</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-40"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQList"><span class="hs-identifier">IQList</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-41"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier">TaggedQueue</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-42"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQList"><span class="hs-identifier">TQList</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-43"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier">IndexedTaggedQueue</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-44"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQList"><span class="hs-identifier">ITQList</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-45"></span><span>  </span><span class="hs-special">,</span><span>
</span><span id="line-46"></span><span>   </span><span class="annot"><span class="hs-comment">-- * Merges</span></span><span>
</span><span id="line-47"></span><span>   </span><span class="annot"><span class="hs-comment">-- $merges</span></span><span>
</span><span id="line-48"></span><span>   </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#mergeQ"><span class="hs-identifier">mergeQ</span></a></span><span>
</span><span id="line-49"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#mergeIQ"><span class="hs-identifier">mergeIQ</span></a></span><span>
</span><span id="line-50"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#mergeTQ"><span class="hs-identifier">mergeTQ</span></a></span><span>
</span><span id="line-51"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#mergeITQ"><span class="hs-identifier">mergeITQ</span></a></span><span>
</span><span id="line-52"></span><span>  </span><span class="hs-special">,</span><span>
</span><span id="line-53"></span><span>   </span><span class="annot"><span class="hs-comment">-- * popMin</span></span><span>
</span><span id="line-54"></span><span>   </span><span class="annot"><span class="hs-comment">-- $popMin</span></span><span>
</span><span id="line-55"></span><span>   </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#popMinQ"><span class="hs-identifier">popMinQ</span></a></span><span>
</span><span id="line-56"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#popMinIQ"><span class="hs-identifier">popMinIQ</span></a></span><span>
</span><span id="line-57"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#popMinTQ"><span class="hs-identifier">popMinTQ</span></a></span><span>
</span><span id="line-58"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#popMinITQ"><span class="hs-identifier">popMinITQ</span></a></span><span>
</span><span id="line-59"></span><span>  </span><span class="hs-special">,</span><span>
</span><span id="line-60"></span><span>   </span><span class="annot"><span class="hs-comment">-- * Building</span></span><span>
</span><span id="line-61"></span><span>   </span><span class="annot"><span class="hs-comment">-- $building</span></span><span>
</span><span id="line-62"></span><span>   </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#buildQ"><span class="hs-identifier">buildQ</span></a></span><span>
</span><span id="line-63"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#buildIQ"><span class="hs-identifier">buildIQ</span></a></span><span>
</span><span id="line-64"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#buildTQ"><span class="hs-identifier">buildTQ</span></a></span><span>
</span><span id="line-65"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#buildITQ"><span class="hs-identifier">buildITQ</span></a></span><span>
</span><span id="line-66"></span><span>  </span><span class="hs-special">,</span><span>
</span><span id="line-67"></span><span>   </span><span class="annot"><span class="hs-comment">-- * Special folds</span></span><span>
</span><span id="line-68"></span><span>   </span><span class="annot"><span class="hs-comment">-- $folds</span></span><span>
</span><span id="line-69"></span><span>   </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeTree"><span class="hs-identifier">foldToMaybeTree</span></a></span><span>
</span><span id="line-70"></span><span>  </span><span class="hs-special">,</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeWithIndexTree"><span class="hs-identifier">foldToMaybeWithIndexTree</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-71"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-72"></span><span>
</span><span id="line-73"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html"><span class="hs-identifier">Data.Sequence.Internal</span></a></span><span>
</span><span id="line-74"></span><span>       </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier">Elem</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier">Seq</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-identifier">Node</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Digit"><span class="hs-identifier">Digit</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Sized"><span class="hs-identifier">Sized</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-identifier">FingerTree</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-75"></span><span>        </span><span class="annot"><a href="Data.Sequence.Internal.html#replicateA"><span class="hs-identifier">replicateA</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#foldDigit"><span class="hs-identifier">foldDigit</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#foldNode"><span class="hs-identifier">foldNode</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#foldWithIndexDigit"><span class="hs-identifier">foldWithIndexDigit</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-76"></span><span>        </span><span class="annot"><a href="Data.Sequence.Internal.html#foldWithIndexNode"><span class="hs-identifier">foldWithIndexNode</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-77"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.State.html"><span class="hs-identifier">Utils.Containers.Internal.State</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Utils.Containers.Internal.State.html#State"><span class="hs-identifier">State</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.State.html#execState"><span class="hs-identifier">execState</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-78"></span><span class="hs-comment">-- | \( O(n \log n) \).  'sort' sorts the specified 'Seq' by the natural</span><span>
</span><span id="line-79"></span><span class="hs-comment">-- ordering of its elements.  The sort is stable.  If stability is not</span><span>
</span><span id="line-80"></span><span class="hs-comment">-- required, 'unstableSort' can be slightly faster.</span><span>
</span><span id="line-81"></span><span class="hs-comment">--</span><span>
</span><span id="line-82"></span><span class="hs-comment">-- @since 0.3.0</span><span>
</span><span id="line-83"></span><span id="local-6989586621679171667"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sort"><span class="hs-identifier hs-type">sort</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679171667"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171667"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171667"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-84"></span><span id="sort"><span class="annot"><span class="annottext">sort :: forall a. Ord a =&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.Sorting.html#sort"><span class="hs-identifier hs-var hs-var">sort</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering) -&gt; Seq a -&gt; Seq a
forall a. (a -&gt; a -&gt; Ordering) -&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.Sorting.html#sortBy"><span class="hs-identifier hs-var">sortBy</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
forall a. Ord a =&gt; a -&gt; a -&gt; Ordering
</span><span class="hs-identifier hs-var">compare</span></span><span>
</span><span id="line-85"></span><span>
</span><span id="line-86"></span><span class="hs-comment">-- | \( O(n \log n) \).  'sortBy' sorts the specified 'Seq' according to the</span><span>
</span><span id="line-87"></span><span class="hs-comment">-- specified comparator.  The sort is stable.  If stability is not required,</span><span>
</span><span id="line-88"></span><span class="hs-comment">-- 'unstableSortBy' can be slightly faster.</span><span>
</span><span id="line-89"></span><span class="hs-comment">--</span><span>
</span><span id="line-90"></span><span class="hs-comment">-- @since 0.3.0</span><span>
</span><span id="line-91"></span><span id="local-6989586621679171664"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sortBy"><span class="hs-identifier hs-type">sortBy</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171664"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171664"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171664"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171664"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-92"></span><span id="sortBy"><span class="annot"><span class="annottext">sortBy :: forall a. (a -&gt; a -&gt; Ordering) -&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.Sorting.html#sortBy"><span class="hs-identifier hs-var hs-var">sortBy</span></a></span></span><span> </span><span id="local-6989586621679171498"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171498"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span id="local-6989586621679171496"><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171496"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-93"></span><span>    </span><span class="annot"><span class="annottext">Seq a
-&gt; (IndexedQueue a -&gt; Seq a) -&gt; Maybe (IndexedQueue a) -&gt; Seq a
forall b a. b -&gt; (a -&gt; b) -&gt; Maybe a -&gt; b
</span><a href="../../base/src/Data.Maybe.html#maybe"><span class="hs-identifier hs-var">maybe</span></a></span><span>
</span><span id="line-94"></span><span>        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">FingerTree (Elem a) -&gt; Seq a
forall a. FingerTree (Elem a) -&gt; Seq a
</span><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-var">Seq</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
forall a. FingerTree a
</span><a href="Data.Sequence.Internal.html#EmptyT"><span class="hs-identifier hs-var">EmptyT</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-95"></span><span>        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">State (IndexedQueue a) (Seq a) -&gt; IndexedQueue a -&gt; Seq a
forall s a. State s a -&gt; s -&gt; a
</span><a href="Utils.Containers.Internal.State.html#execState"><span class="hs-identifier hs-var">execState</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int -&gt; State (IndexedQueue a) a -&gt; State (IndexedQueue a) (Seq a)
forall (f :: * -&gt; *) a. Applicative f =&gt; Int -&gt; f a -&gt; f (Seq a)
</span><a href="Data.Sequence.Internal.html#replicateA"><span class="hs-identifier hs-var">replicateA</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">FingerTree (Elem a) -&gt; Int
forall a. Sized a =&gt; a -&gt; Int
</span><a href="Data.Sequence.Internal.html#size"><span class="hs-identifier hs-var">size</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171496"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(IndexedQueue a -&gt; (IndexedQueue a, a)) -&gt; State (IndexedQueue a) a
forall s a. (s -&gt; (s, a)) -&gt; State s a
</span><a href="Utils.Containers.Internal.State.html#State"><span class="hs-identifier hs-var">State</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering) -&gt; IndexedQueue a -&gt; (IndexedQueue a, a)
forall e.
(e -&gt; e -&gt; Ordering) -&gt; IndexedQueue e -&gt; (IndexedQueue e, e)
</span><a href="Data.Sequence.Internal.Sorting.html#popMinIQ"><span class="hs-identifier hs-var">popMinIQ</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171498"><span class="hs-identifier hs-var">cmp</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-96"></span><span>        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering)
-&gt; (Int -&gt; Elem a -&gt; IndexedQueue a)
-&gt; Int
-&gt; FingerTree (Elem a)
-&gt; Maybe (IndexedQueue a)
forall b y.
(b -&gt; b -&gt; Ordering)
-&gt; (Int -&gt; Elem y -&gt; IndexedQueue b)
-&gt; Int
-&gt; FingerTree (Elem y)
-&gt; Maybe (IndexedQueue b)
</span><a href="Data.Sequence.Internal.Sorting.html#buildIQ"><span class="hs-identifier hs-var">buildIQ</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171498"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621679171491"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171491"><span class="hs-identifier hs-var">s</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span id="local-6989586621679171489"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171489"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; IQList a -&gt; IndexedQueue a
forall e. Int -&gt; e -&gt; IQList e -&gt; IndexedQueue e
</span><a href="Data.Sequence.Internal.Sorting.html#IQ"><span class="hs-identifier hs-var">IQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171491"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171489"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">IQList a
forall e. IQList e
</span><a href="Data.Sequence.Internal.Sorting.html#IQNil"><span class="hs-identifier hs-var">IQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">0</span></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171496"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-97"></span><span>
</span><span id="line-98"></span><span class="hs-comment">-- | \( O(n \log n) \). 'sortOn' sorts the specified 'Seq' by comparing</span><span>
</span><span id="line-99"></span><span class="hs-comment">-- the results of a key function applied to each element. @'sortOn' f@ is</span><span>
</span><span id="line-100"></span><span class="hs-comment">-- equivalent to @'sortBy' ('compare' ``Data.Function.on`` f)@, but has the</span><span>
</span><span id="line-101"></span><span class="hs-comment">-- performance advantage of only evaluating @f@ once for each element in the</span><span>
</span><span id="line-102"></span><span class="hs-comment">-- input list. This is called the decorate-sort-undecorate paradigm, or</span><span>
</span><span id="line-103"></span><span class="hs-comment">-- Schwartzian transform.</span><span>
</span><span id="line-104"></span><span class="hs-comment">--</span><span>
</span><span id="line-105"></span><span class="hs-comment">-- An example of using 'sortOn' might be to sort a 'Seq' of strings</span><span>
</span><span id="line-106"></span><span class="hs-comment">-- according to their length:</span><span>
</span><span id="line-107"></span><span class="hs-comment">--</span><span>
</span><span id="line-108"></span><span class="hs-comment">-- &gt; sortOn length (fromList [&quot;alligator&quot;, &quot;monkey&quot;, &quot;zebra&quot;]) == fromList [&quot;zebra&quot;, &quot;monkey&quot;, &quot;alligator&quot;]</span><span>
</span><span id="line-109"></span><span class="hs-comment">--</span><span>
</span><span id="line-110"></span><span class="hs-comment">-- If, instead, 'sortBy' had been used, 'length' would be evaluated on</span><span>
</span><span id="line-111"></span><span class="hs-comment">-- every comparison, giving \( O(n \log n) \) evaluations, rather than</span><span>
</span><span id="line-112"></span><span class="hs-comment">-- \( O(n) \).</span><span>
</span><span id="line-113"></span><span class="hs-comment">--</span><span>
</span><span id="line-114"></span><span class="hs-comment">-- If @f@ is very cheap (for example a record selector, or 'fst'),</span><span>
</span><span id="line-115"></span><span class="hs-comment">-- @'sortBy' ('compare' ``Data.Function.on`` f)@ will be faster than</span><span>
</span><span id="line-116"></span><span class="hs-comment">-- @'sortOn' f@.</span><span>
</span><span id="line-117"></span><span class="hs-comment">--</span><span>
</span><span id="line-118"></span><span class="hs-comment">-- @since 0.5.11</span><span>
</span><span id="line-119"></span><span id="local-6989586621679171635"><span id="local-6989586621679171636"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sortOn"><span class="hs-identifier hs-type">sortOn</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679171636"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171635"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171636"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171635"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171635"><span class="hs-identifier hs-type">a</span></a></span></span></span><span>
</span><span id="line-120"></span><span id="sortOn"><span class="annot"><span class="annottext">sortOn :: forall b a. Ord b =&gt; (a -&gt; b) -&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.Sorting.html#sortOn"><span class="hs-identifier hs-var hs-var">sortOn</span></a></span></span><span> </span><span id="local-6989586621679171480"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171480"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span id="local-6989586621679171479"><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171479"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-121"></span><span>    </span><span class="annot"><span class="annottext">Seq a
-&gt; (IndexedTaggedQueue b a -&gt; Seq a)
-&gt; Maybe (IndexedTaggedQueue b a)
-&gt; Seq a
forall b a. b -&gt; (a -&gt; b) -&gt; Maybe a -&gt; b
</span><a href="../../base/src/Data.Maybe.html#maybe"><span class="hs-identifier hs-var">maybe</span></a></span><span>
</span><span id="line-122"></span><span>       </span><span class="hs-special">(</span><span class="annot"><span class="annottext">FingerTree (Elem a) -&gt; Seq a
forall a. FingerTree (Elem a) -&gt; Seq a
</span><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-var">Seq</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
forall a. FingerTree a
</span><a href="Data.Sequence.Internal.html#EmptyT"><span class="hs-identifier hs-var">EmptyT</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-123"></span><span>       </span><span class="hs-special">(</span><span class="annot"><span class="annottext">State (IndexedTaggedQueue b a) (Seq a)
-&gt; IndexedTaggedQueue b a -&gt; Seq a
forall s a. State s a -&gt; s -&gt; a
</span><a href="Utils.Containers.Internal.State.html#execState"><span class="hs-identifier hs-var">execState</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int
-&gt; State (IndexedTaggedQueue b a) a
-&gt; State (IndexedTaggedQueue b a) (Seq a)
forall (f :: * -&gt; *) a. Applicative f =&gt; Int -&gt; f a -&gt; f (Seq a)
</span><a href="Data.Sequence.Internal.html#replicateA"><span class="hs-identifier hs-var">replicateA</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">FingerTree (Elem a) -&gt; Int
forall a. Sized a =&gt; a -&gt; Int
</span><a href="Data.Sequence.Internal.html#size"><span class="hs-identifier hs-var">size</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171479"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(IndexedTaggedQueue b a -&gt; (IndexedTaggedQueue b a, a))
-&gt; State (IndexedTaggedQueue b a) a
forall s a. (s -&gt; (s, a)) -&gt; State s a
</span><a href="Utils.Containers.Internal.State.html#State"><span class="hs-identifier hs-var">State</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; Ordering)
-&gt; IndexedTaggedQueue b a -&gt; (IndexedTaggedQueue b a, a)
forall e b.
(e -&gt; e -&gt; Ordering)
-&gt; IndexedTaggedQueue e b -&gt; (IndexedTaggedQueue e b, b)
</span><a href="Data.Sequence.Internal.Sorting.html#popMinITQ"><span class="hs-identifier hs-var">popMinITQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
forall a. Ord a =&gt; a -&gt; a -&gt; Ordering
</span><span class="hs-identifier hs-var">compare</span></span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-124"></span><span>       </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; Ordering)
-&gt; (Int -&gt; Elem a -&gt; IndexedTaggedQueue b a)
-&gt; Int
-&gt; FingerTree (Elem a)
-&gt; Maybe (IndexedTaggedQueue b a)
forall b y c.
(b -&gt; b -&gt; Ordering)
-&gt; (Int -&gt; Elem y -&gt; IndexedTaggedQueue b c)
-&gt; Int
-&gt; FingerTree (Elem y)
-&gt; Maybe (IndexedTaggedQueue b c)
</span><a href="Data.Sequence.Internal.Sorting.html#buildITQ"><span class="hs-identifier hs-var">buildITQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
forall a. Ord a =&gt; a -&gt; a -&gt; Ordering
</span><span class="hs-identifier hs-var">compare</span></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621679171478"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171478"><span class="hs-identifier hs-var">s</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span id="local-6989586621679171477"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171477"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Int -&gt; b -&gt; a -&gt; ITQList b a -&gt; IndexedTaggedQueue b a
forall e a. Int -&gt; e -&gt; a -&gt; ITQList e a -&gt; IndexedTaggedQueue e a
</span><a href="Data.Sequence.Internal.Sorting.html#ITQ"><span class="hs-identifier hs-var">ITQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171478"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171480"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171477"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171477"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList b a
forall e a. ITQList e a
</span><a href="Data.Sequence.Internal.Sorting.html#ITQNil"><span class="hs-identifier hs-var">ITQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">0</span></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171479"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-125"></span><span>
</span><span id="line-126"></span><span class="hs-comment">-- | \( O(n \log n) \).  'unstableSort' sorts the specified 'Seq' by</span><span>
</span><span id="line-127"></span><span class="hs-comment">-- the natural ordering of its elements, but the sort is not stable.</span><span>
</span><span id="line-128"></span><span class="hs-comment">-- This algorithm is frequently faster and uses less memory than 'sort'.</span><span>
</span><span id="line-129"></span><span>
</span><span id="line-130"></span><span class="hs-comment">-- Notes on the implementation and choice of heap are available in</span><span>
</span><span id="line-131"></span><span class="hs-comment">-- the file sorting.md (in this directory).</span><span>
</span><span id="line-132"></span><span class="hs-comment">--</span><span>
</span><span id="line-133"></span><span class="hs-comment">-- @since 0.3.0</span><span>
</span><span id="line-134"></span><span id="local-6989586621679171474"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSort"><span class="hs-identifier hs-type">unstableSort</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679171474"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171474"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171474"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-135"></span><span id="unstableSort"><span class="annot"><span class="annottext">unstableSort :: forall a. Ord a =&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.Sorting.html#unstableSort"><span class="hs-identifier hs-var hs-var">unstableSort</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering) -&gt; Seq a -&gt; Seq a
forall a. (a -&gt; a -&gt; Ordering) -&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.Sorting.html#unstableSortBy"><span class="hs-identifier hs-var">unstableSortBy</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
forall a. Ord a =&gt; a -&gt; a -&gt; Ordering
</span><span class="hs-identifier hs-var">compare</span></span><span>
</span><span id="line-136"></span><span>
</span><span id="line-137"></span><span class="hs-comment">-- | \( O(n \log n) \).  A generalization of 'unstableSort', 'unstableSortBy'</span><span>
</span><span id="line-138"></span><span class="hs-comment">-- takes an arbitrary comparator and sorts the specified sequence.</span><span>
</span><span id="line-139"></span><span class="hs-comment">-- The sort is not stable.  This algorithm is frequently faster and</span><span>
</span><span id="line-140"></span><span class="hs-comment">-- uses less memory than 'sortBy'.</span><span>
</span><span id="line-141"></span><span class="hs-comment">--</span><span>
</span><span id="line-142"></span><span class="hs-comment">-- @since 0.3.0</span><span>
</span><span id="line-143"></span><span id="local-6989586621679171471"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSortBy"><span class="hs-identifier hs-type">unstableSortBy</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171471"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171471"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171471"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171471"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-144"></span><span id="unstableSortBy"><span class="annot"><span class="annottext">unstableSortBy :: forall a. (a -&gt; a -&gt; Ordering) -&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.Sorting.html#unstableSortBy"><span class="hs-identifier hs-var hs-var">unstableSortBy</span></a></span></span><span> </span><span id="local-6989586621679171467"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171467"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span id="local-6989586621679171466"><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171466"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-145"></span><span>    </span><span class="annot"><span class="annottext">Seq a -&gt; (Queue a -&gt; Seq a) -&gt; Maybe (Queue a) -&gt; Seq a
forall b a. b -&gt; (a -&gt; b) -&gt; Maybe a -&gt; b
</span><a href="../../base/src/Data.Maybe.html#maybe"><span class="hs-identifier hs-var">maybe</span></a></span><span>
</span><span id="line-146"></span><span>        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">FingerTree (Elem a) -&gt; Seq a
forall a. FingerTree (Elem a) -&gt; Seq a
</span><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-var">Seq</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
forall a. FingerTree a
</span><a href="Data.Sequence.Internal.html#EmptyT"><span class="hs-identifier hs-var">EmptyT</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-147"></span><span>        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">State (Queue a) (Seq a) -&gt; Queue a -&gt; Seq a
forall s a. State s a -&gt; s -&gt; a
</span><a href="Utils.Containers.Internal.State.html#execState"><span class="hs-identifier hs-var">execState</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int -&gt; State (Queue a) a -&gt; State (Queue a) (Seq a)
forall (f :: * -&gt; *) a. Applicative f =&gt; Int -&gt; f a -&gt; f (Seq a)
</span><a href="Data.Sequence.Internal.html#replicateA"><span class="hs-identifier hs-var">replicateA</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">FingerTree (Elem a) -&gt; Int
forall a. Sized a =&gt; a -&gt; Int
</span><a href="Data.Sequence.Internal.html#size"><span class="hs-identifier hs-var">size</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171466"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Queue a -&gt; (Queue a, a)) -&gt; State (Queue a) a
forall s a. (s -&gt; (s, a)) -&gt; State s a
</span><a href="Utils.Containers.Internal.State.html#State"><span class="hs-identifier hs-var">State</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering) -&gt; Queue a -&gt; (Queue a, a)
forall e. (e -&gt; e -&gt; Ordering) -&gt; Queue e -&gt; (Queue e, e)
</span><a href="Data.Sequence.Internal.Sorting.html#popMinQ"><span class="hs-identifier hs-var">popMinQ</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171467"><span class="hs-identifier hs-var">cmp</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-148"></span><span>        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering)
-&gt; (Elem a -&gt; Queue a) -&gt; FingerTree (Elem a) -&gt; Maybe (Queue a)
forall b a.
(b -&gt; b -&gt; Ordering)
-&gt; (a -&gt; Queue b) -&gt; FingerTree a -&gt; Maybe (Queue b)
</span><a href="Data.Sequence.Internal.Sorting.html#buildQ"><span class="hs-identifier hs-var">buildQ</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171467"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span id="local-6989586621679171465"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171465"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">a -&gt; QList a -&gt; Queue a
forall e. e -&gt; QList e -&gt; Queue e
</span><a href="Data.Sequence.Internal.Sorting.html#Q"><span class="hs-identifier hs-var">Q</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171465"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">QList a
forall e. QList e
</span><a href="Data.Sequence.Internal.Sorting.html#Nil"><span class="hs-identifier hs-var">Nil</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171466"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-149"></span><span>
</span><span id="line-150"></span><span class="hs-comment">-- | \( O(n \log n) \). 'unstableSortOn' sorts the specified 'Seq' by</span><span>
</span><span id="line-151"></span><span class="hs-comment">-- comparing the results of a key function applied to each element.</span><span>
</span><span id="line-152"></span><span class="hs-comment">-- @'unstableSortOn' f@ is equivalent to @'unstableSortBy' ('compare' ``Data.Function.on`` f)@,</span><span>
</span><span id="line-153"></span><span class="hs-comment">-- but has the performance advantage of only evaluating @f@ once for each</span><span>
</span><span id="line-154"></span><span class="hs-comment">-- element in the input list. This is called the</span><span>
</span><span id="line-155"></span><span class="hs-comment">-- decorate-sort-undecorate paradigm, or Schwartzian transform.</span><span>
</span><span id="line-156"></span><span class="hs-comment">--</span><span>
</span><span id="line-157"></span><span class="hs-comment">-- An example of using 'unstableSortOn' might be to sort a 'Seq' of strings</span><span>
</span><span id="line-158"></span><span class="hs-comment">-- according to their length:</span><span>
</span><span id="line-159"></span><span class="hs-comment">--</span><span>
</span><span id="line-160"></span><span class="hs-comment">-- &gt; unstableSortOn length (fromList [&quot;alligator&quot;, &quot;monkey&quot;, &quot;zebra&quot;]) == fromList [&quot;zebra&quot;, &quot;monkey&quot;, &quot;alligator&quot;]</span><span>
</span><span id="line-161"></span><span class="hs-comment">--</span><span>
</span><span id="line-162"></span><span class="hs-comment">-- If, instead, 'unstableSortBy' had been used, 'length' would be evaluated on</span><span>
</span><span id="line-163"></span><span class="hs-comment">-- every comparison, giving \( O(n \log n) \) evaluations, rather than</span><span>
</span><span id="line-164"></span><span class="hs-comment">-- \( O(n) \).</span><span>
</span><span id="line-165"></span><span class="hs-comment">--</span><span>
</span><span id="line-166"></span><span class="hs-comment">-- If @f@ is very cheap (for example a record selector, or 'fst'),</span><span>
</span><span id="line-167"></span><span class="hs-comment">-- @'unstableSortBy' ('compare' ``Data.Function.on`` f)@ will be faster than</span><span>
</span><span id="line-168"></span><span class="hs-comment">-- @'unstableSortOn' f@.</span><span>
</span><span id="line-169"></span><span class="hs-comment">--</span><span>
</span><span id="line-170"></span><span class="hs-comment">-- @since 0.5.11</span><span>
</span><span id="line-171"></span><span id="local-6989586621679171461"><span id="local-6989586621679171462"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSortOn"><span class="hs-identifier hs-type">unstableSortOn</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679171462"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171461"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171462"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171461"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171461"><span class="hs-identifier hs-type">a</span></a></span></span></span><span>
</span><span id="line-172"></span><span id="unstableSortOn"><span class="annot"><span class="annottext">unstableSortOn :: forall b a. Ord b =&gt; (a -&gt; b) -&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.Sorting.html#unstableSortOn"><span class="hs-identifier hs-var hs-var">unstableSortOn</span></a></span></span><span> </span><span id="local-6989586621679171454"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171454"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span id="local-6989586621679171453"><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171453"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-173"></span><span>    </span><span class="annot"><span class="annottext">Seq a
-&gt; (TaggedQueue b a -&gt; Seq a) -&gt; Maybe (TaggedQueue b a) -&gt; Seq a
forall b a. b -&gt; (a -&gt; b) -&gt; Maybe a -&gt; b
</span><a href="../../base/src/Data.Maybe.html#maybe"><span class="hs-identifier hs-var">maybe</span></a></span><span>
</span><span id="line-174"></span><span>       </span><span class="hs-special">(</span><span class="annot"><span class="annottext">FingerTree (Elem a) -&gt; Seq a
forall a. FingerTree (Elem a) -&gt; Seq a
</span><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-var">Seq</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
forall a. FingerTree a
</span><a href="Data.Sequence.Internal.html#EmptyT"><span class="hs-identifier hs-var">EmptyT</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-175"></span><span>       </span><span class="hs-special">(</span><span class="annot"><span class="annottext">State (TaggedQueue b a) (Seq a) -&gt; TaggedQueue b a -&gt; Seq a
forall s a. State s a -&gt; s -&gt; a
</span><a href="Utils.Containers.Internal.State.html#execState"><span class="hs-identifier hs-var">execState</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int -&gt; State (TaggedQueue b a) a -&gt; State (TaggedQueue b a) (Seq a)
forall (f :: * -&gt; *) a. Applicative f =&gt; Int -&gt; f a -&gt; f (Seq a)
</span><a href="Data.Sequence.Internal.html#replicateA"><span class="hs-identifier hs-var">replicateA</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">FingerTree (Elem a) -&gt; Int
forall a. Sized a =&gt; a -&gt; Int
</span><a href="Data.Sequence.Internal.html#size"><span class="hs-identifier hs-var">size</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171453"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(TaggedQueue b a -&gt; (TaggedQueue b a, a))
-&gt; State (TaggedQueue b a) a
forall s a. (s -&gt; (s, a)) -&gt; State s a
</span><a href="Utils.Containers.Internal.State.html#State"><span class="hs-identifier hs-var">State</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; Ordering) -&gt; TaggedQueue b a -&gt; (TaggedQueue b a, a)
forall a b.
(a -&gt; a -&gt; Ordering) -&gt; TaggedQueue a b -&gt; (TaggedQueue a b, b)
</span><a href="Data.Sequence.Internal.Sorting.html#popMinTQ"><span class="hs-identifier hs-var">popMinTQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
forall a. Ord a =&gt; a -&gt; a -&gt; Ordering
</span><span class="hs-identifier hs-var">compare</span></span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-176"></span><span>       </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; Ordering)
-&gt; (Elem a -&gt; TaggedQueue b a)
-&gt; FingerTree (Elem a)
-&gt; Maybe (TaggedQueue b a)
forall b a c.
(b -&gt; b -&gt; Ordering)
-&gt; (a -&gt; TaggedQueue b c)
-&gt; FingerTree a
-&gt; Maybe (TaggedQueue b c)
</span><a href="Data.Sequence.Internal.Sorting.html#buildTQ"><span class="hs-identifier hs-var">buildTQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
forall a. Ord a =&gt; a -&gt; a -&gt; Ordering
</span><span class="hs-identifier hs-var">compare</span></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span id="local-6989586621679171452"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171452"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">b -&gt; a -&gt; TQList b a -&gt; TaggedQueue b a
forall a b. a -&gt; b -&gt; TQList a b -&gt; TaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQ"><span class="hs-identifier hs-var">TQ</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171454"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171452"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171452"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">TQList b a
forall a b. TQList a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQNil"><span class="hs-identifier hs-var">TQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">FingerTree (Elem a)
</span><a href="#local-6989586621679171453"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-177"></span><span>
</span><span id="line-178"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-179"></span><span class="hs-comment">-- $heaps</span><span>
</span><span id="line-180"></span><span class="hs-comment">--</span><span>
</span><span id="line-181"></span><span class="hs-comment">-- The following are definitions for various specialized pairing heaps.</span><span>
</span><span id="line-182"></span><span class="hs-comment">--</span><span>
</span><span id="line-183"></span><span class="hs-comment">-- All of the heaps are defined to be non-empty, which speeds up the</span><span>
</span><span id="line-184"></span><span class="hs-comment">-- merge functions.</span><span>
</span><span id="line-185"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-186"></span><span>
</span><span id="line-187"></span><span class="hs-comment">-- | A simple pairing heap.</span><span>
</span><span id="line-188"></span><span class="hs-keyword">data</span><span> </span><span id="Queue"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-var">Queue</span></a></span></span><span> </span><span id="local-6989586621679171614"><span class="annot"><a href="#local-6989586621679171614"><span class="hs-identifier hs-type">e</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="Q"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Q"><span class="hs-identifier hs-var">Q</span></a></span></span><span> </span><span class="hs-glyph">!</span><span class="annot"><a href="#local-6989586621679171614"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QList"><span class="hs-identifier hs-type">QList</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171614"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-189"></span><span class="hs-keyword">data</span><span> </span><span id="QList"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QList"><span class="hs-identifier hs-var">QList</span></a></span></span><span> </span><span id="local-6989586621679171613"><span class="annot"><a href="#local-6989586621679171613"><span class="hs-identifier hs-type">e</span></a></span></span><span>
</span><span id="line-190"></span><span>    </span><span class="hs-glyph">=</span><span> </span><span id="Nil"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Nil"><span class="hs-identifier hs-var">Nil</span></a></span></span><span>
</span><span id="line-191"></span><span>    </span><span class="hs-glyph">|</span><span> </span><span id="QCons"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-identifier hs-var">QCons</span></a></span></span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-type">Queue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171613"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-192"></span><span>            </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QList"><span class="hs-identifier hs-type">QList</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171613"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-193"></span><span>
</span><span id="line-194"></span><span class="hs-comment">-- | A pairing heap tagged with the original position of elements,</span><span>
</span><span id="line-195"></span><span class="hs-comment">-- to allow for stable sorting.</span><span>
</span><span id="line-196"></span><span class="hs-keyword">data</span><span> </span><span id="IndexedQueue"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-var">IndexedQueue</span></a></span></span><span> </span><span id="local-6989586621679171638"><span class="annot"><a href="#local-6989586621679171638"><span class="hs-identifier hs-type">e</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-197"></span><span>    </span><span id="IQ"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQ"><span class="hs-identifier hs-var">IQ</span></a></span></span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">!</span><span class="annot"><a href="#local-6989586621679171638"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQList"><span class="hs-identifier hs-type">IQList</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171638"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-198"></span><span class="hs-keyword">data</span><span> </span><span id="IQList"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQList"><span class="hs-identifier hs-var">IQList</span></a></span></span><span> </span><span id="local-6989586621679171637"><span class="annot"><a href="#local-6989586621679171637"><span class="hs-identifier hs-type">e</span></a></span></span><span>
</span><span id="line-199"></span><span>    </span><span class="hs-glyph">=</span><span> </span><span id="IQNil"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQNil"><span class="hs-identifier hs-var">IQNil</span></a></span></span><span>
</span><span id="line-200"></span><span>    </span><span class="hs-glyph">|</span><span> </span><span id="IQCons"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-identifier hs-var">IQCons</span></a></span></span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-type">IndexedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171637"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-201"></span><span>             </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQList"><span class="hs-identifier hs-type">IQList</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171637"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-202"></span><span>
</span><span id="line-203"></span><span class="hs-comment">-- | A pairing heap tagged with some key for sorting elements, for use</span><span>
</span><span id="line-204"></span><span class="hs-comment">-- in 'unstableSortOn'.</span><span>
</span><span id="line-205"></span><span class="hs-keyword">data</span><span> </span><span id="TaggedQueue"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-var">TaggedQueue</span></a></span></span><span> </span><span id="local-6989586621679171603"><span class="annot"><a href="#local-6989586621679171603"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span id="local-6989586621679171602"><span class="annot"><a href="#local-6989586621679171602"><span class="hs-identifier hs-type">b</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-206"></span><span>    </span><span id="TQ"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQ"><span class="hs-identifier hs-var">TQ</span></a></span></span><span> </span><span class="hs-glyph">!</span><span class="annot"><a href="#local-6989586621679171603"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171602"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQList"><span class="hs-identifier hs-type">TQList</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171603"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171602"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-207"></span><span class="hs-keyword">data</span><span> </span><span id="TQList"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQList"><span class="hs-identifier hs-var">TQList</span></a></span></span><span> </span><span id="local-6989586621679171601"><span class="annot"><a href="#local-6989586621679171601"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span id="local-6989586621679171600"><span class="annot"><a href="#local-6989586621679171600"><span class="hs-identifier hs-type">b</span></a></span></span><span>
</span><span id="line-208"></span><span>    </span><span class="hs-glyph">=</span><span> </span><span id="TQNil"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQNil"><span class="hs-identifier hs-var">TQNil</span></a></span></span><span>
</span><span id="line-209"></span><span>    </span><span class="hs-glyph">|</span><span> </span><span id="TQCons"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-identifier hs-var">TQCons</span></a></span></span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-type">TaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171601"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171600"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-210"></span><span>             </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQList"><span class="hs-identifier hs-type">TQList</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171601"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171600"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-211"></span><span>
</span><span id="line-212"></span><span class="hs-comment">-- | A pairing heap tagged with both a key and the original position</span><span>
</span><span id="line-213"></span><span class="hs-comment">-- of its elements, for use in 'sortOn'.</span><span>
</span><span id="line-214"></span><span class="hs-keyword">data</span><span> </span><span id="IndexedTaggedQueue"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-var">IndexedTaggedQueue</span></a></span></span><span> </span><span id="local-6989586621679171625"><span class="annot"><a href="#local-6989586621679171625"><span class="hs-identifier hs-type">e</span></a></span></span><span> </span><span id="local-6989586621679171624"><span class="annot"><a href="#local-6989586621679171624"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-215"></span><span>    </span><span id="ITQ"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQ"><span class="hs-identifier hs-var">ITQ</span></a></span></span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">!</span><span class="annot"><a href="#local-6989586621679171625"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171624"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQList"><span class="hs-identifier hs-type">ITQList</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171625"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171624"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-216"></span><span class="hs-keyword">data</span><span> </span><span id="ITQList"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQList"><span class="hs-identifier hs-var">ITQList</span></a></span></span><span> </span><span id="local-6989586621679171623"><span class="annot"><a href="#local-6989586621679171623"><span class="hs-identifier hs-type">e</span></a></span></span><span> </span><span id="local-6989586621679171622"><span class="annot"><a href="#local-6989586621679171622"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-217"></span><span>    </span><span class="hs-glyph">=</span><span> </span><span id="ITQNil"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQNil"><span class="hs-identifier hs-var">ITQNil</span></a></span></span><span>
</span><span id="line-218"></span><span>    </span><span class="hs-glyph">|</span><span> </span><span id="ITQCons"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-identifier hs-var">ITQCons</span></a></span></span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-type">IndexedTaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171623"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171622"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-219"></span><span>              </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQList"><span class="hs-identifier hs-type">ITQList</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171623"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171622"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-220"></span><span>
</span><span id="line-221"></span><span class="hs-keyword">infixr</span><span> </span><span class="hs-number">8</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-type">`ITQCons`</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-operator hs-type">`TQCons`</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-operator hs-type">`QCons`</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-type">`IQCons`</span></a></span><span>
</span><span id="line-222"></span><span>
</span><span id="line-223"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-224"></span><span class="hs-comment">-- $merges</span><span>
</span><span id="line-225"></span><span class="hs-comment">--</span><span>
</span><span id="line-226"></span><span class="hs-comment">-- The following are definitions for &quot;merge&quot; for each of the heaps</span><span>
</span><span id="line-227"></span><span class="hs-comment">-- above. Each takes a comparison function which is used to order the</span><span>
</span><span id="line-228"></span><span class="hs-comment">-- elements.</span><span>
</span><span id="line-229"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-230"></span><span>
</span><span id="line-231"></span><span class="hs-comment">-- | 'mergeQ' merges two 'Queue's.</span><span>
</span><span id="line-232"></span><span id="local-6989586621679171599"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#mergeQ"><span class="hs-identifier hs-type">mergeQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171599"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171599"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-type">Queue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171599"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-type">Queue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171599"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-type">Queue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171599"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-233"></span><span id="mergeQ"><span class="annot"><span class="annottext">mergeQ :: forall a. (a -&gt; a -&gt; Ordering) -&gt; Queue a -&gt; Queue a -&gt; Queue a
</span><a href="Data.Sequence.Internal.Sorting.html#mergeQ"><span class="hs-identifier hs-var hs-var">mergeQ</span></a></span></span><span> </span><span id="local-6989586621679171443"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171443"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span id="local-6989586621679171442"><span class="annot"><span class="annottext">q1 :: Queue a
</span><a href="#local-6989586621679171442"><span class="hs-identifier hs-var">q1</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Q"><span class="hs-identifier hs-type">Q</span></a></span><span> </span><span id="local-6989586621679171441"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171441"><span class="hs-identifier hs-var">x1</span></a></span></span><span> </span><span id="local-6989586621679171440"><span class="annot"><span class="annottext">QList a
</span><a href="#local-6989586621679171440"><span class="hs-identifier hs-var">ts1</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679171439"><span class="annot"><span class="annottext">q2 :: Queue a
</span><a href="#local-6989586621679171439"><span class="hs-identifier hs-var">q2</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Q"><span class="hs-identifier hs-type">Q</span></a></span><span> </span><span id="local-6989586621679171438"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171438"><span class="hs-identifier hs-var">x2</span></a></span></span><span> </span><span id="local-6989586621679171437"><span class="annot"><span class="annottext">QList a
</span><a href="#local-6989586621679171437"><span class="hs-identifier hs-var">ts2</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-234"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171443"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171441"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171438"><span class="hs-identifier hs-var">x2</span></a></span><span> </span><span class="annot"><span class="annottext">Ordering -&gt; Ordering -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">==</span></span><span> </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier hs-var">GT</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; QList a -&gt; Queue a
forall e. e -&gt; QList e -&gt; Queue e
</span><a href="Data.Sequence.Internal.Sorting.html#Q"><span class="hs-identifier hs-var">Q</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171438"><span class="hs-identifier hs-var">x2</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Queue a
</span><a href="#local-6989586621679171442"><span class="hs-identifier hs-var">q1</span></a></span><span> </span><span class="annot"><span class="annottext">Queue a -&gt; QList a -&gt; QList a
forall e. Queue e -&gt; QList e -&gt; QList e
</span><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-operator hs-var">`QCons`</span></a></span><span> </span><span class="annot"><span class="annottext">QList a
</span><a href="#local-6989586621679171437"><span class="hs-identifier hs-var">ts2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-235"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>       </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; QList a -&gt; Queue a
forall e. e -&gt; QList e -&gt; Queue e
</span><a href="Data.Sequence.Internal.Sorting.html#Q"><span class="hs-identifier hs-var">Q</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171441"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Queue a
</span><a href="#local-6989586621679171439"><span class="hs-identifier hs-var">q2</span></a></span><span> </span><span class="annot"><span class="annottext">Queue a -&gt; QList a -&gt; QList a
forall e. Queue e -&gt; QList e -&gt; QList e
</span><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-operator hs-var">`QCons`</span></a></span><span> </span><span class="annot"><span class="annottext">QList a
</span><a href="#local-6989586621679171440"><span class="hs-identifier hs-var">ts1</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-236"></span><span>
</span><span id="line-237"></span><span class="hs-comment">-- | 'mergeTQ' merges two 'TaggedQueue's, based on the tag value.</span><span>
</span><span id="line-238"></span><span id="local-6989586621679171595"><span id="local-6989586621679171596"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#mergeTQ"><span class="hs-identifier hs-type">mergeTQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171596"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171596"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span>
</span><span id="line-239"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-type">TaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171596"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171595"><span class="hs-identifier hs-type">b</span></a></span><span>
</span><span id="line-240"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-type">TaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171596"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171595"><span class="hs-identifier hs-type">b</span></a></span><span>
</span><span id="line-241"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-type">TaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171596"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171595"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-242"></span><span id="mergeTQ"><span class="annot"><span class="annottext">mergeTQ :: forall a b.
(a -&gt; a -&gt; Ordering)
-&gt; TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#mergeTQ"><span class="hs-identifier hs-var hs-var">mergeTQ</span></a></span></span><span> </span><span id="local-6989586621679171435"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171435"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span id="local-6989586621679171434"><span class="annot"><span class="annottext">q1 :: TaggedQueue a b
</span><a href="#local-6989586621679171434"><span class="hs-identifier hs-var">q1</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQ"><span class="hs-identifier hs-type">TQ</span></a></span><span> </span><span id="local-6989586621679171433"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171433"><span class="hs-identifier hs-var">x1</span></a></span></span><span> </span><span id="local-6989586621679171432"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171432"><span class="hs-identifier hs-var">y1</span></a></span></span><span> </span><span id="local-6989586621679171431"><span class="annot"><span class="annottext">TQList a b
</span><a href="#local-6989586621679171431"><span class="hs-identifier hs-var">ts1</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679171430"><span class="annot"><span class="annottext">q2 :: TaggedQueue a b
</span><a href="#local-6989586621679171430"><span class="hs-identifier hs-var">q2</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQ"><span class="hs-identifier hs-type">TQ</span></a></span><span> </span><span id="local-6989586621679171429"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171429"><span class="hs-identifier hs-var">x2</span></a></span></span><span> </span><span id="local-6989586621679171428"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171428"><span class="hs-identifier hs-var">y2</span></a></span></span><span> </span><span id="local-6989586621679171427"><span class="annot"><span class="annottext">TQList a b
</span><a href="#local-6989586621679171427"><span class="hs-identifier hs-var">ts2</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-243"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171435"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171433"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171429"><span class="hs-identifier hs-var">x2</span></a></span><span> </span><span class="annot"><span class="annottext">Ordering -&gt; Ordering -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">==</span></span><span> </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier hs-var">GT</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; TQList a b -&gt; TaggedQueue a b
forall a b. a -&gt; b -&gt; TQList a b -&gt; TaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQ"><span class="hs-identifier hs-var">TQ</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171429"><span class="hs-identifier hs-var">x2</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171428"><span class="hs-identifier hs-var">y2</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171434"><span class="hs-identifier hs-var">q1</span></a></span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b -&gt; TQList a b -&gt; TQList a b
forall a b. TaggedQueue a b -&gt; TQList a b -&gt; TQList a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-operator hs-var">`TQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">TQList a b
</span><a href="#local-6989586621679171427"><span class="hs-identifier hs-var">ts2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-244"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>       </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; TQList a b -&gt; TaggedQueue a b
forall a b. a -&gt; b -&gt; TQList a b -&gt; TaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQ"><span class="hs-identifier hs-var">TQ</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171433"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171432"><span class="hs-identifier hs-var">y1</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171430"><span class="hs-identifier hs-var">q2</span></a></span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b -&gt; TQList a b -&gt; TQList a b
forall a b. TaggedQueue a b -&gt; TQList a b -&gt; TQList a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-operator hs-var">`TQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">TQList a b
</span><a href="#local-6989586621679171431"><span class="hs-identifier hs-var">ts1</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-245"></span><span>
</span><span id="line-246"></span><span class="hs-comment">-- | 'mergeIQ' merges two 'IndexedQueue's, taking into account the</span><span>
</span><span id="line-247"></span><span class="hs-comment">-- original position of the elements.</span><span>
</span><span id="line-248"></span><span id="local-6989586621679171592"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#mergeIQ"><span class="hs-identifier hs-type">mergeIQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171592"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171592"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span>
</span><span id="line-249"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-type">IndexedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171592"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-250"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-type">IndexedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171592"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-251"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-type">IndexedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171592"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-252"></span><span id="mergeIQ"><span class="annot"><span class="annottext">mergeIQ :: forall a.
(a -&gt; a -&gt; Ordering)
-&gt; IndexedQueue a -&gt; IndexedQueue a -&gt; IndexedQueue a
</span><a href="Data.Sequence.Internal.Sorting.html#mergeIQ"><span class="hs-identifier hs-var hs-var">mergeIQ</span></a></span></span><span> </span><span id="local-6989586621679171424"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171424"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span id="local-6989586621679171423"><span class="annot"><span class="annottext">q1 :: IndexedQueue a
</span><a href="#local-6989586621679171423"><span class="hs-identifier hs-var">q1</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQ"><span class="hs-identifier hs-type">IQ</span></a></span><span> </span><span id="local-6989586621679171422"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171422"><span class="hs-identifier hs-var">i1</span></a></span></span><span> </span><span id="local-6989586621679171421"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171421"><span class="hs-identifier hs-var">x1</span></a></span></span><span> </span><span id="local-6989586621679171420"><span class="annot"><span class="annottext">IQList a
</span><a href="#local-6989586621679171420"><span class="hs-identifier hs-var">ts1</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679171419"><span class="annot"><span class="annottext">q2 :: IndexedQueue a
</span><a href="#local-6989586621679171419"><span class="hs-identifier hs-var">q2</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQ"><span class="hs-identifier hs-type">IQ</span></a></span><span> </span><span id="local-6989586621679171418"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171418"><span class="hs-identifier hs-var">i2</span></a></span></span><span> </span><span id="local-6989586621679171417"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171417"><span class="hs-identifier hs-var">x2</span></a></span></span><span> </span><span id="local-6989586621679171416"><span class="annot"><span class="annottext">IQList a
</span><a href="#local-6989586621679171416"><span class="hs-identifier hs-var">ts2</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-253"></span><span>    </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171424"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171421"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171417"><span class="hs-identifier hs-var">x2</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-254"></span><span>        </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier hs-var">LT</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; IQList a -&gt; IndexedQueue a
forall e. Int -&gt; e -&gt; IQList e -&gt; IndexedQueue e
</span><a href="Data.Sequence.Internal.Sorting.html#IQ"><span class="hs-identifier hs-var">IQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171422"><span class="hs-identifier hs-var">i1</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171421"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IndexedQueue a
</span><a href="#local-6989586621679171419"><span class="hs-identifier hs-var">q2</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedQueue a -&gt; IQList a -&gt; IQList a
forall e. IndexedQueue e -&gt; IQList e -&gt; IQList e
</span><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-var">`IQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">IQList a
</span><a href="#local-6989586621679171420"><span class="hs-identifier hs-var">ts1</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-255"></span><span>        </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier hs-var">EQ</span></span><span> </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171422"><span class="hs-identifier hs-var">i1</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&lt;=</span></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171418"><span class="hs-identifier hs-var">i2</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; IQList a -&gt; IndexedQueue a
forall e. Int -&gt; e -&gt; IQList e -&gt; IndexedQueue e
</span><a href="Data.Sequence.Internal.Sorting.html#IQ"><span class="hs-identifier hs-var">IQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171422"><span class="hs-identifier hs-var">i1</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171421"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IndexedQueue a
</span><a href="#local-6989586621679171419"><span class="hs-identifier hs-var">q2</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedQueue a -&gt; IQList a -&gt; IQList a
forall e. IndexedQueue e -&gt; IQList e -&gt; IQList e
</span><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-var">`IQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">IQList a
</span><a href="#local-6989586621679171420"><span class="hs-identifier hs-var">ts1</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-256"></span><span>        </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; IQList a -&gt; IndexedQueue a
forall e. Int -&gt; e -&gt; IQList e -&gt; IndexedQueue e
</span><a href="Data.Sequence.Internal.Sorting.html#IQ"><span class="hs-identifier hs-var">IQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171418"><span class="hs-identifier hs-var">i2</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171417"><span class="hs-identifier hs-var">x2</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IndexedQueue a
</span><a href="#local-6989586621679171423"><span class="hs-identifier hs-var">q1</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedQueue a -&gt; IQList a -&gt; IQList a
forall e. IndexedQueue e -&gt; IQList e -&gt; IQList e
</span><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-var">`IQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">IQList a
</span><a href="#local-6989586621679171416"><span class="hs-identifier hs-var">ts2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-257"></span><span>
</span><span id="line-258"></span><span class="hs-comment">-- | 'mergeITQ' merges two 'IndexedTaggedQueue's, based on the tag</span><span>
</span><span id="line-259"></span><span class="hs-comment">-- value, taking into account the original position of the elements.</span><span>
</span><span id="line-260"></span><span id="local-6989586621679171589"><span id="local-6989586621679171590"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#mergeITQ"><span class="hs-identifier hs-type">mergeITQ</span></a></span><span>
</span><span id="line-261"></span><span>    </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171590"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171590"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span>
</span><span id="line-262"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-type">IndexedTaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171590"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171589"><span class="hs-identifier hs-type">b</span></a></span><span>
</span><span id="line-263"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-type">IndexedTaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171590"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171589"><span class="hs-identifier hs-type">b</span></a></span><span>
</span><span id="line-264"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-type">IndexedTaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171590"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171589"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-265"></span><span id="mergeITQ"><span class="annot"><span class="annottext">mergeITQ :: forall a b.
(a -&gt; a -&gt; Ordering)
-&gt; IndexedTaggedQueue a b
-&gt; IndexedTaggedQueue a b
-&gt; IndexedTaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#mergeITQ"><span class="hs-identifier hs-var hs-var">mergeITQ</span></a></span></span><span> </span><span id="local-6989586621679171413"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171413"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span id="local-6989586621679171412"><span class="annot"><span class="annottext">q1 :: IndexedTaggedQueue a b
</span><a href="#local-6989586621679171412"><span class="hs-identifier hs-var">q1</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQ"><span class="hs-identifier hs-type">ITQ</span></a></span><span> </span><span id="local-6989586621679171411"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171411"><span class="hs-identifier hs-var">i1</span></a></span></span><span> </span><span id="local-6989586621679171410"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171410"><span class="hs-identifier hs-var">x1</span></a></span></span><span> </span><span id="local-6989586621679171409"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171409"><span class="hs-identifier hs-var">y1</span></a></span></span><span> </span><span id="local-6989586621679171408"><span class="annot"><span class="annottext">ITQList a b
</span><a href="#local-6989586621679171408"><span class="hs-identifier hs-var">ts1</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679171407"><span class="annot"><span class="annottext">q2 :: IndexedTaggedQueue a b
</span><a href="#local-6989586621679171407"><span class="hs-identifier hs-var">q2</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQ"><span class="hs-identifier hs-type">ITQ</span></a></span><span> </span><span id="local-6989586621679171406"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171406"><span class="hs-identifier hs-var">i2</span></a></span></span><span> </span><span id="local-6989586621679171405"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171405"><span class="hs-identifier hs-var">x2</span></a></span></span><span> </span><span id="local-6989586621679171404"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171404"><span class="hs-identifier hs-var">y2</span></a></span></span><span> </span><span id="local-6989586621679171403"><span class="annot"><span class="annottext">ITQList a b
</span><a href="#local-6989586621679171403"><span class="hs-identifier hs-var">ts2</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-266"></span><span>    </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171413"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171410"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171405"><span class="hs-identifier hs-var">x2</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-267"></span><span>        </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier hs-var">LT</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; b -&gt; ITQList a b -&gt; IndexedTaggedQueue a b
forall e a. Int -&gt; e -&gt; a -&gt; ITQList e a -&gt; IndexedTaggedQueue e a
</span><a href="Data.Sequence.Internal.Sorting.html#ITQ"><span class="hs-identifier hs-var">ITQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171411"><span class="hs-identifier hs-var">i1</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171410"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171409"><span class="hs-identifier hs-var">y1</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IndexedTaggedQueue a b
</span><a href="#local-6989586621679171407"><span class="hs-identifier hs-var">q2</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue a b -&gt; ITQList a b -&gt; ITQList a b
forall e a. IndexedTaggedQueue e a -&gt; ITQList e a -&gt; ITQList e a
</span><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-var">`ITQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList a b
</span><a href="#local-6989586621679171408"><span class="hs-identifier hs-var">ts1</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-268"></span><span>        </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier hs-var">EQ</span></span><span> </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171411"><span class="hs-identifier hs-var">i1</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&lt;=</span></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171406"><span class="hs-identifier hs-var">i2</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; b -&gt; ITQList a b -&gt; IndexedTaggedQueue a b
forall e a. Int -&gt; e -&gt; a -&gt; ITQList e a -&gt; IndexedTaggedQueue e a
</span><a href="Data.Sequence.Internal.Sorting.html#ITQ"><span class="hs-identifier hs-var">ITQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171411"><span class="hs-identifier hs-var">i1</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171410"><span class="hs-identifier hs-var">x1</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171409"><span class="hs-identifier hs-var">y1</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IndexedTaggedQueue a b
</span><a href="#local-6989586621679171407"><span class="hs-identifier hs-var">q2</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue a b -&gt; ITQList a b -&gt; ITQList a b
forall e a. IndexedTaggedQueue e a -&gt; ITQList e a -&gt; ITQList e a
</span><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-var">`ITQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList a b
</span><a href="#local-6989586621679171408"><span class="hs-identifier hs-var">ts1</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-269"></span><span>        </span><span class="annot"><span class="annottext">Ordering
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; b -&gt; ITQList a b -&gt; IndexedTaggedQueue a b
forall e a. Int -&gt; e -&gt; a -&gt; ITQList e a -&gt; IndexedTaggedQueue e a
</span><a href="Data.Sequence.Internal.Sorting.html#ITQ"><span class="hs-identifier hs-var">ITQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171406"><span class="hs-identifier hs-var">i2</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171405"><span class="hs-identifier hs-var">x2</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171404"><span class="hs-identifier hs-var">y2</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IndexedTaggedQueue a b
</span><a href="#local-6989586621679171412"><span class="hs-identifier hs-var">q1</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue a b -&gt; ITQList a b -&gt; ITQList a b
forall e a. IndexedTaggedQueue e a -&gt; ITQList e a -&gt; ITQList e a
</span><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-var">`ITQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList a b
</span><a href="#local-6989586621679171403"><span class="hs-identifier hs-var">ts2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-270"></span><span>
</span><span id="line-271"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-272"></span><span class="hs-comment">-- $popMin</span><span>
</span><span id="line-273"></span><span class="hs-comment">--</span><span>
</span><span id="line-274"></span><span class="hs-comment">-- The following are definitions for @popMin@, a function which</span><span>
</span><span id="line-275"></span><span class="hs-comment">-- constructs a stateful action which pops the smallest element from the</span><span>
</span><span id="line-276"></span><span class="hs-comment">-- queue, where &quot;smallest&quot; is according to the supplied comparison</span><span>
</span><span id="line-277"></span><span class="hs-comment">-- function.</span><span>
</span><span id="line-278"></span><span class="hs-comment">--</span><span>
</span><span id="line-279"></span><span class="hs-comment">-- All of the functions fail on an empty queue.</span><span>
</span><span id="line-280"></span><span class="hs-comment">--</span><span>
</span><span id="line-281"></span><span class="hs-comment">-- Each of these functions is structured something like this:</span><span>
</span><span id="line-282"></span><span class="hs-comment">--</span><span>
</span><span id="line-283"></span><span class="hs-comment">-- @popMinQ cmp (Q x ts) = (mergeQs ts, x)@</span><span>
</span><span id="line-284"></span><span class="hs-comment">--</span><span>
</span><span id="line-285"></span><span class="hs-comment">-- The reason the call to @mergeQs@ is lazy is that it will be bottom</span><span>
</span><span id="line-286"></span><span class="hs-comment">-- for the last element in the queue, preventing us from evaluating the</span><span>
</span><span id="line-287"></span><span class="hs-comment">-- fully sorted sequence.</span><span>
</span><span id="line-288"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-289"></span><span>
</span><span id="line-290"></span><span class="hs-comment">-- | Pop the smallest element from the queue, using the supplied</span><span>
</span><span id="line-291"></span><span class="hs-comment">-- comparator.</span><span>
</span><span id="line-292"></span><span id="local-6989586621679171618"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#popMinQ"><span class="hs-identifier hs-type">popMinQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171618"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171618"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-type">Queue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171618"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-type">Queue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171618"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621679171618"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">)</span></span><span>
</span><span id="line-293"></span><span id="popMinQ"><span class="annot"><span class="annottext">popMinQ :: forall e. (e -&gt; e -&gt; Ordering) -&gt; Queue e -&gt; (Queue e, e)
</span><a href="Data.Sequence.Internal.Sorting.html#popMinQ"><span class="hs-identifier hs-var hs-var">popMinQ</span></a></span></span><span> </span><span id="local-6989586621679171402"><span class="annot"><span class="annottext">e -&gt; e -&gt; Ordering
</span><a href="#local-6989586621679171402"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Q"><span class="hs-identifier hs-type">Q</span></a></span><span> </span><span id="local-6989586621679171401"><span class="annot"><span class="annottext">e
</span><a href="#local-6989586621679171401"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171400"><span class="annot"><span class="annottext">QList e
</span><a href="#local-6989586621679171400"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">QList e -&gt; Queue e
</span><a href="#local-6989586621679171399"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">QList e
</span><a href="#local-6989586621679171400"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">e
</span><a href="#local-6989586621679171401"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-294"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-295"></span><span>    </span><span id="local-6989586621679171399"><span class="annot"><span class="annottext">mergeQs :: QList e -&gt; Queue e
</span><a href="#local-6989586621679171399"><span class="hs-identifier hs-var hs-var">mergeQs</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171396"><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171396"><span class="hs-identifier hs-var">t</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-operator hs-type">`QCons`</span></a></span><span> </span><span class="annot"><span class="annottext">QList e
</span><a href="Data.Sequence.Internal.Sorting.html#Nil"><span class="hs-identifier hs-var">Nil</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171396"><span class="hs-identifier hs-var">t</span></a></span><span>
</span><span id="line-296"></span><span>    </span><span class="annot"><a href="#local-6989586621679171399"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171395"><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171395"><span class="hs-identifier hs-var">t1</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-operator hs-type">`QCons`</span></a></span><span> </span><span id="local-6989586621679171394"><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171394"><span class="hs-identifier hs-var">t2</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-operator hs-type">`QCons`</span></a></span><span> </span><span class="annot"><span class="annottext">QList e
</span><a href="Data.Sequence.Internal.Sorting.html#Nil"><span class="hs-identifier hs-var">Nil</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171395"><span class="hs-identifier hs-var">t1</span></a></span><span> </span><span class="annot"><span class="annottext">Queue e -&gt; Queue e -&gt; Queue e
</span><a href="#local-6989586621679171393"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171394"><span class="hs-identifier hs-var">t2</span></a></span><span>
</span><span id="line-297"></span><span>    </span><span class="annot"><a href="#local-6989586621679171399"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171392"><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171392"><span class="hs-identifier hs-var">t1</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-operator hs-type">`QCons`</span></a></span><span> </span><span id="local-6989586621679171391"><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171391"><span class="hs-identifier hs-var">t2</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#QCons"><span class="hs-operator hs-type">`QCons`</span></a></span><span> </span><span id="local-6989586621679171390"><span class="annot"><span class="annottext">QList e
</span><a href="#local-6989586621679171390"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171392"><span class="hs-identifier hs-var">t1</span></a></span><span> </span><span class="annot"><span class="annottext">Queue e -&gt; Queue e -&gt; Queue e
</span><a href="#local-6989586621679171393"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">Queue e
</span><a href="#local-6989586621679171391"><span class="hs-identifier hs-var">t2</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Queue e -&gt; Queue e -&gt; Queue e
</span><a href="#local-6989586621679171393"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">QList e -&gt; Queue e
</span><a href="#local-6989586621679171399"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">QList e
</span><a href="#local-6989586621679171390"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-298"></span><span>    </span><span class="annot"><a href="#local-6989586621679171399"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">QList e
</span><a href="Data.Sequence.Internal.Sorting.html#Nil"><span class="hs-identifier hs-var">Nil</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; Queue e
forall a. HasCallStack =&gt; [Char] -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;popMinQ: tried to pop from empty queue&quot;</span></span><span>
</span><span id="line-299"></span><span>    </span><span id="local-6989586621679171393"><span class="annot"><span class="annottext">&lt;+&gt; :: Queue e -&gt; Queue e -&gt; Queue e
</span><a href="#local-6989586621679171393"><span class="hs-operator hs-var hs-var">(&lt;+&gt;)</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(e -&gt; e -&gt; Ordering) -&gt; Queue e -&gt; Queue e -&gt; Queue e
forall a. (a -&gt; a -&gt; Ordering) -&gt; Queue a -&gt; Queue a -&gt; Queue a
</span><a href="Data.Sequence.Internal.Sorting.html#mergeQ"><span class="hs-identifier hs-var">mergeQ</span></a></span><span> </span><span class="annot"><span class="annottext">e -&gt; e -&gt; Ordering
</span><a href="#local-6989586621679171402"><span class="hs-identifier hs-var">cmp</span></a></span><span>
</span><span id="line-300"></span><span>
</span><span id="line-301"></span><span class="hs-comment">-- | Pop the smallest element from the queue, using the supplied</span><span>
</span><span id="line-302"></span><span class="hs-comment">-- comparator, deferring to the item's original position when the</span><span>
</span><span id="line-303"></span><span class="hs-comment">-- comparator returns 'EQ'.</span><span>
</span><span id="line-304"></span><span id="local-6989586621679171642"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#popMinIQ"><span class="hs-identifier hs-type">popMinIQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171642"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171642"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-type">IndexedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171642"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-type">IndexedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171642"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621679171642"><span class="hs-identifier hs-type">e</span></a></span><span class="hs-special">)</span></span><span>
</span><span id="line-305"></span><span id="popMinIQ"><span class="annot"><span class="annottext">popMinIQ :: forall e.
(e -&gt; e -&gt; Ordering) -&gt; IndexedQueue e -&gt; (IndexedQueue e, e)
</span><a href="Data.Sequence.Internal.Sorting.html#popMinIQ"><span class="hs-identifier hs-var hs-var">popMinIQ</span></a></span></span><span> </span><span id="local-6989586621679171388"><span class="annot"><span class="annottext">e -&gt; e -&gt; Ordering
</span><a href="#local-6989586621679171388"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQ"><span class="hs-identifier hs-type">IQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679171387"><span class="annot"><span class="annottext">e
</span><a href="#local-6989586621679171387"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171386"><span class="annot"><span class="annottext">IQList e
</span><a href="#local-6989586621679171386"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IQList e -&gt; IndexedQueue e
</span><a href="#local-6989586621679171385"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">IQList e
</span><a href="#local-6989586621679171386"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">e
</span><a href="#local-6989586621679171387"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-306"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-307"></span><span>    </span><span id="local-6989586621679171385"><span class="annot"><span class="annottext">mergeQs :: IQList e -&gt; IndexedQueue e
</span><a href="#local-6989586621679171385"><span class="hs-identifier hs-var hs-var">mergeQs</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171382"><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171382"><span class="hs-identifier hs-var">t</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-type">`IQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">IQList e
</span><a href="Data.Sequence.Internal.Sorting.html#IQNil"><span class="hs-identifier hs-var">IQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171382"><span class="hs-identifier hs-var">t</span></a></span><span>
</span><span id="line-308"></span><span>    </span><span class="annot"><a href="#local-6989586621679171385"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171381"><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171381"><span class="hs-identifier hs-var">t1</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-type">`IQCons`</span></a></span><span> </span><span id="local-6989586621679171380"><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171380"><span class="hs-identifier hs-var">t2</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-type">`IQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">IQList e
</span><a href="Data.Sequence.Internal.Sorting.html#IQNil"><span class="hs-identifier hs-var">IQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171381"><span class="hs-identifier hs-var">t1</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedQueue e -&gt; IndexedQueue e -&gt; IndexedQueue e
</span><a href="#local-6989586621679171379"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171380"><span class="hs-identifier hs-var">t2</span></a></span><span>
</span><span id="line-309"></span><span>    </span><span class="annot"><a href="#local-6989586621679171385"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171378"><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171378"><span class="hs-identifier hs-var">t1</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-type">`IQCons`</span></a></span><span> </span><span id="local-6989586621679171377"><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171377"><span class="hs-identifier hs-var">t2</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IQCons"><span class="hs-operator hs-type">`IQCons`</span></a></span><span> </span><span id="local-6989586621679171376"><span class="annot"><span class="annottext">IQList e
</span><a href="#local-6989586621679171376"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171378"><span class="hs-identifier hs-var">t1</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedQueue e -&gt; IndexedQueue e -&gt; IndexedQueue e
</span><a href="#local-6989586621679171379"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedQueue e
</span><a href="#local-6989586621679171377"><span class="hs-identifier hs-var">t2</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">IndexedQueue e -&gt; IndexedQueue e -&gt; IndexedQueue e
</span><a href="#local-6989586621679171379"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">IQList e -&gt; IndexedQueue e
</span><a href="#local-6989586621679171385"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">IQList e
</span><a href="#local-6989586621679171376"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-310"></span><span>    </span><span class="annot"><a href="#local-6989586621679171385"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">IQList e
</span><a href="Data.Sequence.Internal.Sorting.html#IQNil"><span class="hs-identifier hs-var">IQNil</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; IndexedQueue e
forall a. HasCallStack =&gt; [Char] -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;popMinQ: tried to pop from empty queue&quot;</span></span><span>
</span><span id="line-311"></span><span>    </span><span id="local-6989586621679171379"><span class="annot"><span class="annottext">&lt;+&gt; :: IndexedQueue e -&gt; IndexedQueue e -&gt; IndexedQueue e
</span><a href="#local-6989586621679171379"><span class="hs-operator hs-var hs-var">(&lt;+&gt;)</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(e -&gt; e -&gt; Ordering)
-&gt; IndexedQueue e -&gt; IndexedQueue e -&gt; IndexedQueue e
forall a.
(a -&gt; a -&gt; Ordering)
-&gt; IndexedQueue a -&gt; IndexedQueue a -&gt; IndexedQueue a
</span><a href="Data.Sequence.Internal.Sorting.html#mergeIQ"><span class="hs-identifier hs-var">mergeIQ</span></a></span><span> </span><span class="annot"><span class="annottext">e -&gt; e -&gt; Ordering
</span><a href="#local-6989586621679171388"><span class="hs-identifier hs-var">cmp</span></a></span><span>
</span><span id="line-312"></span><span>
</span><span id="line-313"></span><span class="hs-comment">-- | Pop the smallest element from the queue, using the supplied</span><span>
</span><span id="line-314"></span><span class="hs-comment">-- comparator on the tag.</span><span>
</span><span id="line-315"></span><span id="local-6989586621679171608"><span id="local-6989586621679171609"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#popMinTQ"><span class="hs-identifier hs-type">popMinTQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171609"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171609"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-type">TaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171609"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171608"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-type">TaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171609"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171608"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621679171608"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-316"></span><span id="popMinTQ"><span class="annot"><span class="annottext">popMinTQ :: forall a b.
(a -&gt; a -&gt; Ordering) -&gt; TaggedQueue a b -&gt; (TaggedQueue a b, b)
</span><a href="Data.Sequence.Internal.Sorting.html#popMinTQ"><span class="hs-identifier hs-var hs-var">popMinTQ</span></a></span></span><span> </span><span id="local-6989586621679171375"><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171375"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQ"><span class="hs-identifier hs-type">TQ</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679171374"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171374"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171373"><span class="annot"><span class="annottext">TQList a b
</span><a href="#local-6989586621679171373"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">TQList a b -&gt; TaggedQueue a b
forall {b}. TQList a b -&gt; TaggedQueue a b
</span><a href="#local-6989586621679171372"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">TQList a b
</span><a href="#local-6989586621679171373"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171374"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-317"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-318"></span><span>    </span><span id="local-6989586621679171372"><span class="annot"><span class="annottext">mergeQs :: TQList a b -&gt; TaggedQueue a b
</span><a href="#local-6989586621679171372"><span class="hs-identifier hs-var hs-var">mergeQs</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171369"><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171369"><span class="hs-identifier hs-var">t</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-operator hs-type">`TQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">TQList a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQNil"><span class="hs-identifier hs-var">TQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171369"><span class="hs-identifier hs-var">t</span></a></span><span>
</span><span id="line-319"></span><span>    </span><span class="annot"><a href="#local-6989586621679171372"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171368"><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171368"><span class="hs-identifier hs-var">t1</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-operator hs-type">`TQCons`</span></a></span><span> </span><span id="local-6989586621679171367"><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171367"><span class="hs-identifier hs-var">t2</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-operator hs-type">`TQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">TQList a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQNil"><span class="hs-identifier hs-var">TQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171368"><span class="hs-identifier hs-var">t1</span></a></span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
forall {b}. TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
</span><a href="#local-6989586621679171366"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171367"><span class="hs-identifier hs-var">t2</span></a></span><span>
</span><span id="line-320"></span><span>    </span><span class="annot"><a href="#local-6989586621679171372"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171365"><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171365"><span class="hs-identifier hs-var">t1</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-operator hs-type">`TQCons`</span></a></span><span> </span><span id="local-6989586621679171364"><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171364"><span class="hs-identifier hs-var">t2</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TQCons"><span class="hs-operator hs-type">`TQCons`</span></a></span><span> </span><span id="local-6989586621679171363"><span class="annot"><span class="annottext">TQList a b
</span><a href="#local-6989586621679171363"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171365"><span class="hs-identifier hs-var">t1</span></a></span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
forall {b}. TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
</span><a href="#local-6989586621679171366"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b
</span><a href="#local-6989586621679171364"><span class="hs-identifier hs-var">t2</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
forall {b}. TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
</span><a href="#local-6989586621679171366"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">TQList a b -&gt; TaggedQueue a b
</span><a href="#local-6989586621679171372"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">TQList a b
</span><a href="#local-6989586621679171363"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-321"></span><span>    </span><span class="annot"><a href="#local-6989586621679171372"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">TQList a b
</span><a href="Data.Sequence.Internal.Sorting.html#TQNil"><span class="hs-identifier hs-var">TQNil</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; TaggedQueue a b
forall a. HasCallStack =&gt; [Char] -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;popMinQ: tried to pop from empty queue&quot;</span></span><span>
</span><span id="line-322"></span><span>    </span><span id="local-6989586621679171366"><span class="annot"><span class="annottext">&lt;+&gt; :: TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
</span><a href="#local-6989586621679171366"><span class="hs-operator hs-var hs-var">(&lt;+&gt;)</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; Ordering)
-&gt; TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
forall a b.
(a -&gt; a -&gt; Ordering)
-&gt; TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#mergeTQ"><span class="hs-identifier hs-var">mergeTQ</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; Ordering
</span><a href="#local-6989586621679171375"><span class="hs-identifier hs-var">cmp</span></a></span><span>
</span><span id="line-323"></span><span>
</span><span id="line-324"></span><span class="hs-comment">-- | Pop the smallest element from the queue, using the supplied</span><span>
</span><span id="line-325"></span><span class="hs-comment">-- comparator on the tag, deferring to the item's original position</span><span>
</span><span id="line-326"></span><span class="hs-comment">-- when the comparator returns 'EQ'.</span><span>
</span><span id="line-327"></span><span id="local-6989586621679171630"><span id="local-6989586621679171631"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#popMinITQ"><span class="hs-identifier hs-type">popMinITQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171631"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171631"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span>
</span><span id="line-328"></span><span>          </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-type">IndexedTaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171631"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171630"><span class="hs-identifier hs-type">b</span></a></span><span>
</span><span id="line-329"></span><span>          </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-type">IndexedTaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171631"><span class="hs-identifier hs-type">e</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171630"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621679171630"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-330"></span><span id="popMinITQ"><span class="annot"><span class="annottext">popMinITQ :: forall e b.
(e -&gt; e -&gt; Ordering)
-&gt; IndexedTaggedQueue e b -&gt; (IndexedTaggedQueue e b, b)
</span><a href="Data.Sequence.Internal.Sorting.html#popMinITQ"><span class="hs-identifier hs-var hs-var">popMinITQ</span></a></span></span><span> </span><span id="local-6989586621679171362"><span class="annot"><span class="annottext">e -&gt; e -&gt; Ordering
</span><a href="#local-6989586621679171362"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQ"><span class="hs-identifier hs-type">ITQ</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">e
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679171361"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171361"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171360"><span class="annot"><span class="annottext">ITQList e b
</span><a href="#local-6989586621679171360"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">ITQList e b -&gt; IndexedTaggedQueue e b
forall {b}. ITQList e b -&gt; IndexedTaggedQueue e b
</span><a href="#local-6989586621679171359"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList e b
</span><a href="#local-6989586621679171360"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171361"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-331"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-332"></span><span>    </span><span id="local-6989586621679171359"><span class="annot"><span class="annottext">mergeQs :: ITQList e b -&gt; IndexedTaggedQueue e b
</span><a href="#local-6989586621679171359"><span class="hs-identifier hs-var hs-var">mergeQs</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171356"><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171356"><span class="hs-identifier hs-var">t</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-type">`ITQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList e b
</span><a href="Data.Sequence.Internal.Sorting.html#ITQNil"><span class="hs-identifier hs-var">ITQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171356"><span class="hs-identifier hs-var">t</span></a></span><span>
</span><span id="line-333"></span><span>    </span><span class="annot"><a href="#local-6989586621679171359"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171355"><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171355"><span class="hs-identifier hs-var">t1</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-type">`ITQCons`</span></a></span><span> </span><span id="local-6989586621679171354"><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171354"><span class="hs-identifier hs-var">t2</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-type">`ITQCons`</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList e b
</span><a href="Data.Sequence.Internal.Sorting.html#ITQNil"><span class="hs-identifier hs-var">ITQNil</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171355"><span class="hs-identifier hs-var">t1</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b -&gt; IndexedTaggedQueue e b
forall {b}.
IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b -&gt; IndexedTaggedQueue e b
</span><a href="#local-6989586621679171353"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171354"><span class="hs-identifier hs-var">t2</span></a></span><span>
</span><span id="line-334"></span><span>    </span><span class="annot"><a href="#local-6989586621679171359"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171352"><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171352"><span class="hs-identifier hs-var">t1</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-type">`ITQCons`</span></a></span><span> </span><span id="local-6989586621679171351"><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171351"><span class="hs-identifier hs-var">t2</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#ITQCons"><span class="hs-operator hs-type">`ITQCons`</span></a></span><span> </span><span id="local-6989586621679171350"><span class="annot"><span class="annottext">ITQList e b
</span><a href="#local-6989586621679171350"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171352"><span class="hs-identifier hs-var">t1</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b -&gt; IndexedTaggedQueue e b
forall {b}.
IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b -&gt; IndexedTaggedQueue e b
</span><a href="#local-6989586621679171353"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue e b
</span><a href="#local-6989586621679171351"><span class="hs-identifier hs-var">t2</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b -&gt; IndexedTaggedQueue e b
forall {b}.
IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b -&gt; IndexedTaggedQueue e b
</span><a href="#local-6989586621679171353"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList e b -&gt; IndexedTaggedQueue e b
</span><a href="#local-6989586621679171359"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList e b
</span><a href="#local-6989586621679171350"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-335"></span><span>    </span><span class="annot"><a href="#local-6989586621679171359"><span class="hs-identifier hs-var">mergeQs</span></a></span><span> </span><span class="annot"><span class="annottext">ITQList e b
</span><a href="Data.Sequence.Internal.Sorting.html#ITQNil"><span class="hs-identifier hs-var">ITQNil</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; IndexedTaggedQueue e b
forall a. HasCallStack =&gt; [Char] -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;popMinQ: tried to pop from empty queue&quot;</span></span><span>
</span><span id="line-336"></span><span>    </span><span id="local-6989586621679171353"><span class="annot"><span class="annottext">&lt;+&gt; :: IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b -&gt; IndexedTaggedQueue e b
</span><a href="#local-6989586621679171353"><span class="hs-operator hs-var hs-var">(&lt;+&gt;)</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(e -&gt; e -&gt; Ordering)
-&gt; IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b
-&gt; IndexedTaggedQueue e b
forall a b.
(a -&gt; a -&gt; Ordering)
-&gt; IndexedTaggedQueue a b
-&gt; IndexedTaggedQueue a b
-&gt; IndexedTaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#mergeITQ"><span class="hs-identifier hs-var">mergeITQ</span></a></span><span> </span><span class="annot"><span class="annottext">e -&gt; e -&gt; Ordering
</span><a href="#local-6989586621679171362"><span class="hs-identifier hs-var">cmp</span></a></span><span>
</span><span id="line-337"></span><span>
</span><span id="line-338"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-339"></span><span class="hs-comment">-- $building</span><span>
</span><span id="line-340"></span><span class="hs-comment">--</span><span>
</span><span id="line-341"></span><span class="hs-comment">-- The following are definitions for functions to build queues, given a</span><span>
</span><span id="line-342"></span><span class="hs-comment">-- comparison function.</span><span>
</span><span id="line-343"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-344"></span><span>
</span><span id="line-345"></span><span id="local-6989586621679171616"><span id="local-6989586621679171617"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#buildQ"><span class="hs-identifier hs-type">buildQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171617"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171617"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171616"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-type">Queue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171617"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-identifier hs-type">FingerTree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171616"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#Queue"><span class="hs-identifier hs-type">Queue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171617"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-346"></span><span id="buildQ"><span class="annot"><span class="annottext">buildQ :: forall b a.
(b -&gt; b -&gt; Ordering)
-&gt; (a -&gt; Queue b) -&gt; FingerTree a -&gt; Maybe (Queue b)
</span><a href="Data.Sequence.Internal.Sorting.html#buildQ"><span class="hs-identifier hs-var hs-var">buildQ</span></a></span></span><span> </span><span id="local-6989586621679171349"><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679171349"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Queue b -&gt; Queue b -&gt; Queue b)
-&gt; (a -&gt; Queue b) -&gt; FingerTree a -&gt; Maybe (Queue b)
forall b a. (b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; FingerTree a -&gt; Maybe b
</span><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeTree"><span class="hs-identifier hs-var">foldToMaybeTree</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; Ordering) -&gt; Queue b -&gt; Queue b -&gt; Queue b
forall a. (a -&gt; a -&gt; Ordering) -&gt; Queue a -&gt; Queue a -&gt; Queue a
</span><a href="Data.Sequence.Internal.Sorting.html#mergeQ"><span class="hs-identifier hs-var">mergeQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679171349"><span class="hs-identifier hs-var">cmp</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-347"></span><span>
</span><span id="line-348"></span><span id="local-6989586621679171640"><span id="local-6989586621679171641"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#buildIQ"><span class="hs-identifier hs-type">buildIQ</span></a></span><span>
</span><span id="line-349"></span><span>    </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171641"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171641"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span>
</span><span id="line-350"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171640"><span class="hs-identifier hs-type">y</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-type">IndexedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171641"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-351"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span>
</span><span id="line-352"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-identifier hs-type">FingerTree</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171640"><span class="hs-identifier hs-type">y</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-353"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedQueue"><span class="hs-identifier hs-type">IndexedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171641"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-354"></span><span id="buildIQ"><span class="annot"><span class="annottext">buildIQ :: forall b y.
(b -&gt; b -&gt; Ordering)
-&gt; (Int -&gt; Elem y -&gt; IndexedQueue b)
-&gt; Int
-&gt; FingerTree (Elem y)
-&gt; Maybe (IndexedQueue b)
</span><a href="Data.Sequence.Internal.Sorting.html#buildIQ"><span class="hs-identifier hs-var hs-var">buildIQ</span></a></span></span><span> </span><span id="local-6989586621679171348"><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679171348"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(IndexedQueue b -&gt; IndexedQueue b -&gt; IndexedQueue b)
-&gt; (Int -&gt; Elem y -&gt; IndexedQueue b)
-&gt; Int
-&gt; FingerTree (Elem y)
-&gt; Maybe (IndexedQueue b)
forall b y.
(b -&gt; b -&gt; b)
-&gt; (Int -&gt; Elem y -&gt; b) -&gt; Int -&gt; FingerTree (Elem y) -&gt; Maybe b
</span><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeWithIndexTree"><span class="hs-identifier hs-var">foldToMaybeWithIndexTree</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; Ordering)
-&gt; IndexedQueue b -&gt; IndexedQueue b -&gt; IndexedQueue b
forall a.
(a -&gt; a -&gt; Ordering)
-&gt; IndexedQueue a -&gt; IndexedQueue a -&gt; IndexedQueue a
</span><a href="Data.Sequence.Internal.Sorting.html#mergeIQ"><span class="hs-identifier hs-var">mergeIQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679171348"><span class="hs-identifier hs-var">cmp</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-355"></span><span>
</span><span id="line-356"></span><span id="local-6989586621679171605"><span id="local-6989586621679171606"><span id="local-6989586621679171607"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#buildTQ"><span class="hs-identifier hs-type">buildTQ</span></a></span><span>
</span><span id="line-357"></span><span>    </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171607"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171607"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span>
</span><span id="line-358"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171606"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-type">TaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171607"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171605"><span class="hs-identifier hs-type">c</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-359"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-identifier hs-type">FingerTree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171606"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-360"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#TaggedQueue"><span class="hs-identifier hs-type">TaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171607"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171605"><span class="hs-identifier hs-type">c</span></a></span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-361"></span><span id="buildTQ"><span class="annot"><span class="annottext">buildTQ :: forall b a c.
(b -&gt; b -&gt; Ordering)
-&gt; (a -&gt; TaggedQueue b c)
-&gt; FingerTree a
-&gt; Maybe (TaggedQueue b c)
</span><a href="Data.Sequence.Internal.Sorting.html#buildTQ"><span class="hs-identifier hs-var hs-var">buildTQ</span></a></span></span><span> </span><span id="local-6989586621679171347"><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679171347"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(TaggedQueue b c -&gt; TaggedQueue b c -&gt; TaggedQueue b c)
-&gt; (a -&gt; TaggedQueue b c)
-&gt; FingerTree a
-&gt; Maybe (TaggedQueue b c)
forall b a. (b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; FingerTree a -&gt; Maybe b
</span><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeTree"><span class="hs-identifier hs-var">foldToMaybeTree</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; Ordering)
-&gt; TaggedQueue b c -&gt; TaggedQueue b c -&gt; TaggedQueue b c
forall a b.
(a -&gt; a -&gt; Ordering)
-&gt; TaggedQueue a b -&gt; TaggedQueue a b -&gt; TaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#mergeTQ"><span class="hs-identifier hs-var">mergeTQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679171347"><span class="hs-identifier hs-var">cmp</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-362"></span><span>
</span><span id="line-363"></span><span id="local-6989586621679171627"><span id="local-6989586621679171628"><span id="local-6989586621679171629"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#buildITQ"><span class="hs-identifier hs-type">buildITQ</span></a></span><span>
</span><span id="line-364"></span><span>    </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171629"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171629"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ordering</span></span><span class="hs-special">)</span><span>
</span><span id="line-365"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171628"><span class="hs-identifier hs-type">y</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-type">IndexedTaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171629"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171627"><span class="hs-identifier hs-type">c</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-366"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span>
</span><span id="line-367"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-identifier hs-type">FingerTree</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171628"><span class="hs-identifier hs-type">y</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-368"></span><span>    </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#IndexedTaggedQueue"><span class="hs-identifier hs-type">IndexedTaggedQueue</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171629"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171627"><span class="hs-identifier hs-type">c</span></a></span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-369"></span><span id="buildITQ"><span class="annot"><span class="annottext">buildITQ :: forall b y c.
(b -&gt; b -&gt; Ordering)
-&gt; (Int -&gt; Elem y -&gt; IndexedTaggedQueue b c)
-&gt; Int
-&gt; FingerTree (Elem y)
-&gt; Maybe (IndexedTaggedQueue b c)
</span><a href="Data.Sequence.Internal.Sorting.html#buildITQ"><span class="hs-identifier hs-var hs-var">buildITQ</span></a></span></span><span> </span><span id="local-6989586621679171346"><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679171346"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(IndexedTaggedQueue b c
 -&gt; IndexedTaggedQueue b c -&gt; IndexedTaggedQueue b c)
-&gt; (Int -&gt; Elem y -&gt; IndexedTaggedQueue b c)
-&gt; Int
-&gt; FingerTree (Elem y)
-&gt; Maybe (IndexedTaggedQueue b c)
forall b y.
(b -&gt; b -&gt; b)
-&gt; (Int -&gt; Elem y -&gt; b) -&gt; Int -&gt; FingerTree (Elem y) -&gt; Maybe b
</span><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeWithIndexTree"><span class="hs-identifier hs-var">foldToMaybeWithIndexTree</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; Ordering)
-&gt; IndexedTaggedQueue b c
-&gt; IndexedTaggedQueue b c
-&gt; IndexedTaggedQueue b c
forall a b.
(a -&gt; a -&gt; Ordering)
-&gt; IndexedTaggedQueue a b
-&gt; IndexedTaggedQueue a b
-&gt; IndexedTaggedQueue a b
</span><a href="Data.Sequence.Internal.Sorting.html#mergeITQ"><span class="hs-identifier hs-var">mergeITQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679171346"><span class="hs-identifier hs-var">cmp</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-370"></span><span>
</span><span id="line-371"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-372"></span><span class="hs-comment">-- $folds</span><span>
</span><span id="line-373"></span><span class="hs-comment">--</span><span>
</span><span id="line-374"></span><span class="hs-comment">-- A big part of what makes the heaps fast is that they're non empty,</span><span>
</span><span id="line-375"></span><span class="hs-comment">-- so the merge function can avoid an extra case match. To take</span><span>
</span><span id="line-376"></span><span class="hs-comment">-- advantage of this, though, we need specialized versions of 'foldMap'</span><span>
</span><span id="line-377"></span><span class="hs-comment">-- and 'Data.Sequence.foldMapWithIndex', which can alternate between</span><span>
</span><span id="line-378"></span><span class="hs-comment">-- calling the faster semigroup-like merge when folding over non empty</span><span>
</span><span id="line-379"></span><span class="hs-comment">-- structures (like 'Node' and 'Digit'), and the</span><span>
</span><span id="line-380"></span><span class="hs-comment">-- 'Data.Semirgroup.Option'-like mappend, when folding over structures</span><span>
</span><span id="line-381"></span><span class="hs-comment">-- which can be empty (like 'FingerTree').</span><span>
</span><span id="line-382"></span><span class="hs-comment">------------------------------------------------------------------------</span><span>
</span><span id="line-383"></span><span>
</span><span id="line-384"></span><span class="hs-comment">-- | A 'foldMap'-like function, specialized to the</span><span>
</span><span id="line-385"></span><span class="hs-comment">-- 'Data.Semigroup.Option' monoid, which takes advantage of the</span><span>
</span><span id="line-386"></span><span class="hs-comment">-- internal structure of 'Seq' to avoid wrapping in 'Maybe' at certain</span><span>
</span><span id="line-387"></span><span class="hs-comment">-- points.</span><span>
</span><span id="line-388"></span><span id="local-6989586621679171570"><span id="local-6989586621679171571"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeTree"><span class="hs-identifier hs-type">foldToMaybeTree</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171571"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171571"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171571"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171570"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171571"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-identifier hs-type">FingerTree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171570"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171571"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-389"></span><span id="foldToMaybeTree"><span class="annot"><span class="annottext">foldToMaybeTree :: forall b a. (b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; FingerTree a -&gt; Maybe b
</span><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeTree"><span class="hs-identifier hs-var hs-var">foldToMaybeTree</span></a></span></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">a -&gt; b
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">FingerTree a
</span><a href="Data.Sequence.Internal.html#EmptyT"><span class="hs-identifier hs-var">EmptyT</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Maybe b
forall a. Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span>
</span><span id="line-390"></span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeTree"><span class="hs-identifier hs-var">foldToMaybeTree</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679171345"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171345"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Single"><span class="hs-identifier hs-type">Single</span></a></span><span> </span><span id="local-6989586621679171343"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171343"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b -&gt; Maybe b
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171345"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171343"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-391"></span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeTree"><span class="hs-identifier hs-var">foldToMaybeTree</span></a></span><span> </span><span id="local-6989586621679171342"><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171342"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span></span><span> </span><span id="local-6989586621679171341"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171341"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Deep"><span class="hs-identifier hs-type">Deep</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679171339"><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171339"><span class="hs-identifier hs-var">pr</span></a></span></span><span> </span><span id="local-6989586621679171338"><span class="annot"><span class="annottext">FingerTree (Node a)
</span><a href="#local-6989586621679171338"><span class="hs-identifier hs-var">m</span></a></span></span><span> </span><span id="local-6989586621679171337"><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171337"><span class="hs-identifier hs-var">sf</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-392"></span><span>    </span><span class="annot"><span class="annottext">b -&gt; Maybe b
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b -&gt; (b -&gt; b) -&gt; Maybe b -&gt; b
forall b a. b -&gt; (a -&gt; b) -&gt; Maybe a -&gt; b
</span><a href="../../base/src/Data.Maybe.html#maybe"><span class="hs-identifier hs-var">maybe</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171336"><span class="hs-identifier hs-var">pr'</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171342"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171335"><span class="hs-identifier hs-var">sf'</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="hs-special">(</span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171336"><span class="hs-identifier hs-var">pr'</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171342"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171335"><span class="hs-identifier hs-var">sf'</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171342"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Maybe b
</span><a href="#local-6989586621679171334"><span class="hs-identifier hs-var">m'</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-393"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-394"></span><span>    </span><span id="local-6989586621679171336"><span class="annot"><span class="annottext">pr' :: b
</span><a href="#local-6989586621679171336"><span class="hs-identifier hs-var hs-var">pr'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; Digit a -&gt; b
forall b a. (b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; Digit a -&gt; b
</span><a href="Data.Sequence.Internal.html#foldDigit"><span class="hs-identifier hs-var">foldDigit</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171342"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171341"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171339"><span class="hs-identifier hs-var">pr</span></a></span><span>
</span><span id="line-395"></span><span>    </span><span id="local-6989586621679171335"><span class="annot"><span class="annottext">sf' :: b
</span><a href="#local-6989586621679171335"><span class="hs-identifier hs-var hs-var">sf'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; Digit a -&gt; b
forall b a. (b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; Digit a -&gt; b
</span><a href="Data.Sequence.Internal.html#foldDigit"><span class="hs-identifier hs-var">foldDigit</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171342"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171341"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171337"><span class="hs-identifier hs-var">sf</span></a></span><span>
</span><span id="line-396"></span><span>    </span><span id="local-6989586621679171334"><span class="annot"><span class="annottext">m' :: Maybe b
</span><a href="#local-6989586621679171334"><span class="hs-identifier hs-var hs-var">m'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (Node a -&gt; b) -&gt; FingerTree (Node a) -&gt; Maybe b
forall b a. (b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; FingerTree a -&gt; Maybe b
</span><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeTree"><span class="hs-identifier hs-var">foldToMaybeTree</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171342"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; Node a -&gt; b
forall b a. (b -&gt; b -&gt; b) -&gt; (a -&gt; b) -&gt; Node a -&gt; b
</span><a href="Data.Sequence.Internal.html#foldNode"><span class="hs-identifier hs-var">foldNode</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171342"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679171341"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">FingerTree (Node a)
</span><a href="#local-6989586621679171338"><span class="hs-identifier hs-var">m</span></a></span><span>
</span><span id="line-397"></span><span>
</span><span id="line-398"></span><span class="hs-comment">-- | A 'Data.Sequence.foldMapWithIndex'-like function, specialized to the</span><span>
</span><span id="line-399"></span><span class="hs-comment">-- 'Data.Semigroup.Option' monoid, which takes advantage of the</span><span>
</span><span id="line-400"></span><span class="hs-comment">-- internal structure of 'Seq' to avoid wrapping in 'Maybe' at certain</span><span>
</span><span id="line-401"></span><span class="hs-comment">-- points.</span><span>
</span><span id="line-402"></span><span id="local-6989586621679171566"><span id="local-6989586621679171567"><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeWithIndexTree"><span class="hs-identifier hs-type">foldToMaybeWithIndexTree</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171567"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171567"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171567"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-403"></span><span>                         </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171566"><span class="hs-identifier hs-type">y</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171567"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-404"></span><span>                         </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span>
</span><span id="line-405"></span><span>                         </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-identifier hs-type">FingerTree</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-identifier hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171566"><span class="hs-identifier hs-type">y</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-406"></span><span>                         </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171567"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-407"></span><span id="foldToMaybeWithIndexTree"><span class="annot"><span class="annottext">foldToMaybeWithIndexTree :: forall b y.
(b -&gt; b -&gt; b)
-&gt; (Int -&gt; Elem y -&gt; b) -&gt; Int -&gt; FingerTree (Elem y) -&gt; Maybe b
</span><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeWithIndexTree"><span class="hs-identifier hs-var hs-var">foldToMaybeWithIndexTree</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b)
-&gt; (Int -&gt; Elem y -&gt; b) -&gt; Int -&gt; FingerTree (Elem y) -&gt; Maybe b
forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; FingerTree a -&gt; Maybe b
</span><a href="#local-6989586621679171332"><span class="hs-identifier hs-var">foldToMaybeWithIndexTree'</span></a></span><span>
</span><span id="line-408"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-409"></span><span>    </span><span id="local-6989586621679171330"><span id="local-6989586621679171331"><span class="hs-pragma">{-# SPECIALISE</span><span> </span><span class="annot"><a href="#local-6989586621679171332"><span class="hs-pragma hs-type">foldToMaybeWithIndexTree'</span></a></span><span> </span><span class="hs-pragma">::</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="#local-6989586621679171331"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171331"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171331"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="hs-pragma">(</span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-pragma hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171330"><span class="hs-pragma hs-type">y</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171331"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-pragma hs-type">FingerTree</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-pragma hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171330"><span class="hs-pragma hs-type">y</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-pragma hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171331"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">#-}</span></span></span><span>
</span><span id="line-410"></span><span>    </span><span id="local-6989586621679171328"><span id="local-6989586621679171329"><span class="hs-pragma">{-# SPECIALISE</span><span> </span><span class="annot"><a href="#local-6989586621679171332"><span class="hs-pragma hs-type">foldToMaybeWithIndexTree'</span></a></span><span> </span><span class="hs-pragma">::</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="#local-6989586621679171329"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171329"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171329"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="hs-pragma">(</span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-pragma hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171328"><span class="hs-pragma hs-type">y</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171329"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-pragma hs-type">FingerTree</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-pragma hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171328"><span class="hs-pragma hs-type">y</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-pragma hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171329"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">#-}</span></span></span><span>
</span><span id="line-411"></span><span>    </span><span id="local-6989586621679171547"><span id="local-6989586621679171548"><span class="annot"><a href="#local-6989586621679171332"><span class="hs-identifier hs-type">foldToMaybeWithIndexTree'</span></a></span><span>
</span><span id="line-412"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Sized"><span class="hs-identifier hs-type">Sized</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171548"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-413"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171547"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171547"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171547"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171548"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171547"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#FingerTree"><span class="hs-identifier hs-type">FingerTree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171548"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171547"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-414"></span><span>    </span><span id="local-6989586621679171332"><span class="annot"><span class="annottext">foldToMaybeWithIndexTree' :: forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; FingerTree a -&gt; Maybe b
</span><a href="#local-6989586621679171332"><span class="hs-identifier hs-var hs-var">foldToMaybeWithIndexTree'</span></a></span></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; b
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">!</span><span id="local-6989586621679171326"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171326"><span class="hs-identifier hs-var">_s</span></a></span></span><span> </span><span class="annot"><span class="annottext">FingerTree a
</span><a href="Data.Sequence.Internal.html#EmptyT"><span class="hs-identifier hs-var">EmptyT</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Maybe b
forall a. Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span>
</span><span id="line-415"></span><span>    </span><span class="annot"><a href="#local-6989586621679171332"><span class="hs-identifier hs-var">foldToMaybeWithIndexTree'</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679171325"><span class="annot"><span class="annottext">Int -&gt; a -&gt; b
</span><a href="#local-6989586621679171325"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679171324"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171324"><span class="hs-identifier hs-var">s</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Single"><span class="hs-identifier hs-type">Single</span></a></span><span> </span><span id="local-6989586621679171323"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171323"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b -&gt; Maybe b
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int -&gt; a -&gt; b
</span><a href="#local-6989586621679171325"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171324"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171323"><span class="hs-identifier hs-var">xs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-416"></span><span>    </span><span class="annot"><a href="#local-6989586621679171332"><span class="hs-identifier hs-var">foldToMaybeWithIndexTree'</span></a></span><span> </span><span id="local-6989586621679171322"><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171322"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span></span><span> </span><span id="local-6989586621679171321"><span class="annot"><span class="annottext">Int -&gt; a -&gt; b
</span><a href="#local-6989586621679171321"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679171320"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171320"><span class="hs-identifier hs-var">s</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Deep"><span class="hs-identifier hs-type">Deep</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679171319"><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171319"><span class="hs-identifier hs-var">pr</span></a></span></span><span> </span><span id="local-6989586621679171318"><span class="annot"><span class="annottext">FingerTree (Node a)
</span><a href="#local-6989586621679171318"><span class="hs-identifier hs-var">m</span></a></span></span><span> </span><span id="local-6989586621679171317"><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171317"><span class="hs-identifier hs-var">sf</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-417"></span><span>        </span><span class="annot"><span class="annottext">b -&gt; Maybe b
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b -&gt; (b -&gt; b) -&gt; Maybe b -&gt; b
forall b a. b -&gt; (a -&gt; b) -&gt; Maybe a -&gt; b
</span><a href="../../base/src/Data.Maybe.html#maybe"><span class="hs-identifier hs-var">maybe</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171316"><span class="hs-identifier hs-var">pr'</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171322"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171315"><span class="hs-identifier hs-var">sf'</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="hs-special">(</span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171316"><span class="hs-identifier hs-var">pr'</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171322"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171315"><span class="hs-identifier hs-var">sf'</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171322"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Maybe b
</span><a href="#local-6989586621679171314"><span class="hs-identifier hs-var">m'</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-418"></span><span>      </span><span class="hs-keyword">where</span><span>
</span><span id="line-419"></span><span>        </span><span id="local-6989586621679171316"><span class="annot"><span class="annottext">pr' :: b
</span><a href="#local-6989586621679171316"><span class="hs-identifier hs-var hs-var">pr'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Digit a -&gt; b
forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Digit a -&gt; b
</span><a href="#local-6989586621679171312"><span class="hs-identifier hs-var">digit</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171322"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; b
</span><a href="#local-6989586621679171321"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171320"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171319"><span class="hs-identifier hs-var">pr</span></a></span><span>
</span><span id="line-420"></span><span>        </span><span id="local-6989586621679171315"><span class="annot"><span class="annottext">sf' :: b
</span><a href="#local-6989586621679171315"><span class="hs-identifier hs-var hs-var">sf'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Digit a -&gt; b
forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Digit a -&gt; b
</span><a href="#local-6989586621679171312"><span class="hs-identifier hs-var">digit</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171322"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; b
</span><a href="#local-6989586621679171321"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171310"><span class="hs-identifier hs-var">sPsprm</span></a></span><span> </span><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171317"><span class="hs-identifier hs-var">sf</span></a></span><span>
</span><span id="line-421"></span><span>        </span><span id="local-6989586621679171314"><span class="annot"><span class="annottext">m' :: Maybe b
</span><a href="#local-6989586621679171314"><span class="hs-identifier hs-var hs-var">m'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b)
-&gt; (Int -&gt; Node a -&gt; b) -&gt; Int -&gt; FingerTree (Node a) -&gt; Maybe b
forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; FingerTree a -&gt; Maybe b
</span><a href="#local-6989586621679171332"><span class="hs-identifier hs-var">foldToMaybeWithIndexTree'</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171322"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Node a -&gt; b
forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Node a -&gt; b
</span><a href="#local-6989586621679171306"><span class="hs-identifier hs-var">node</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; b -&gt; b
</span><a href="#local-6989586621679171322"><span class="hs-operator hs-var">(&lt;+&gt;)</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; b
</span><a href="#local-6989586621679171321"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171305"><span class="hs-identifier hs-var">sPspr</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Node a)
</span><a href="#local-6989586621679171318"><span class="hs-identifier hs-var">m</span></a></span><span>
</span><span id="line-422"></span><span>        </span><span class="hs-glyph">!</span><span id="local-6989586621679171305"><span class="annot"><span class="annottext">sPspr :: Int
</span><a href="#local-6989586621679171305"><span class="hs-identifier hs-var hs-var">sPspr</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171320"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Int
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#%2B"><span class="hs-operator hs-var">+</span></a></span><span> </span><span class="annot"><span class="annottext">Digit a -&gt; Int
forall a. Sized a =&gt; a -&gt; Int
</span><a href="Data.Sequence.Internal.html#size"><span class="hs-identifier hs-var">size</span></a></span><span> </span><span class="annot"><span class="annottext">Digit a
</span><a href="#local-6989586621679171319"><span class="hs-identifier hs-var">pr</span></a></span><span>
</span><span id="line-423"></span><span>        </span><span class="hs-glyph">!</span><span id="local-6989586621679171310"><span class="annot"><span class="annottext">sPsprm :: Int
</span><a href="#local-6989586621679171310"><span class="hs-identifier hs-var hs-var">sPsprm</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171305"><span class="hs-identifier hs-var">sPspr</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Int
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#%2B"><span class="hs-operator hs-var">+</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Node a) -&gt; Int
forall a. Sized a =&gt; a -&gt; Int
</span><a href="Data.Sequence.Internal.html#size"><span class="hs-identifier hs-var">size</span></a></span><span> </span><span class="annot"><span class="annottext">FingerTree (Node a)
</span><a href="#local-6989586621679171318"><span class="hs-identifier hs-var">m</span></a></span><span>
</span><span id="line-424"></span><span>    </span><span id="local-6989586621679171294"><span id="local-6989586621679171295"><span class="hs-pragma">{-# SPECIALISE</span><span> </span><span class="annot"><a href="#local-6989586621679171312"><span class="hs-pragma hs-type">digit</span></a></span><span> </span><span class="hs-pragma">::</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="#local-6989586621679171295"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171295"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171295"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="hs-pragma">(</span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-pragma hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171294"><span class="hs-pragma hs-type">y</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171295"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Digit"><span class="hs-pragma hs-type">Digit</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-pragma hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171294"><span class="hs-pragma hs-type">y</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171295"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">#-}</span></span></span><span>
</span><span id="line-425"></span><span>    </span><span id="local-6989586621679171292"><span id="local-6989586621679171293"><span class="hs-pragma">{-# SPECIALISE</span><span> </span><span class="annot"><a href="#local-6989586621679171312"><span class="hs-pragma hs-type">digit</span></a></span><span> </span><span class="hs-pragma">::</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="#local-6989586621679171293"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171293"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171293"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="hs-pragma">(</span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-pragma hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171292"><span class="hs-pragma hs-type">y</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171293"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Digit"><span class="hs-pragma hs-type">Digit</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-pragma hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171292"><span class="hs-pragma hs-type">y</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171293"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">#-}</span></span></span><span>
</span><span id="line-426"></span><span>    </span><span id="local-6989586621679171543"><span id="local-6989586621679171544"><span class="annot"><a href="#local-6989586621679171312"><span class="hs-identifier hs-type">digit</span></a></span><span>
</span><span id="line-427"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Sized"><span class="hs-identifier hs-type">Sized</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171544"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-428"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171543"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171543"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171543"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171544"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171543"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Digit"><span class="hs-identifier hs-type">Digit</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171544"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171543"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-429"></span><span>    </span><span id="local-6989586621679171312"><span class="annot"><span class="annottext">digit :: forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Digit a -&gt; b
</span><a href="#local-6989586621679171312"><span class="hs-identifier hs-var hs-var">digit</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Digit a -&gt; b
forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Digit a -&gt; b
</span><a href="Data.Sequence.Internal.html#foldWithIndexDigit"><span class="hs-identifier hs-var">foldWithIndexDigit</span></a></span><span>
</span><span id="line-430"></span><span>    </span><span id="local-6989586621679171288"><span id="local-6989586621679171289"><span class="hs-pragma">{-# SPECIALISE</span><span> </span><span class="annot"><a href="#local-6989586621679171306"><span class="hs-pragma hs-type">node</span></a></span><span> </span><span class="hs-pragma">::</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="#local-6989586621679171289"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171289"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171289"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="hs-pragma">(</span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-pragma hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171288"><span class="hs-pragma hs-type">y</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171289"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-pragma hs-type">Node</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Elem"><span class="hs-pragma hs-type">Elem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171288"><span class="hs-pragma hs-type">y</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171289"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">#-}</span></span></span><span>
</span><span id="line-431"></span><span>    </span><span id="local-6989586621679171286"><span id="local-6989586621679171287"><span class="hs-pragma">{-# SPECIALISE</span><span> </span><span class="annot"><a href="#local-6989586621679171306"><span class="hs-pragma hs-type">node</span></a></span><span> </span><span class="hs-pragma">::</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="#local-6989586621679171287"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171287"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171287"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="hs-pragma">(</span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-pragma hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171286"><span class="hs-pragma hs-type">y</span></a></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171287"><span class="hs-pragma hs-type">b</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><span class="hs-pragma hs-type">Int</span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-pragma hs-type">Node</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-pragma hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171286"><span class="hs-pragma hs-type">y</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171287"><span class="hs-pragma hs-type">b</span></a></span><span> </span><span class="hs-pragma">#-}</span></span></span><span>
</span><span id="line-432"></span><span>    </span><span id="local-6989586621679171540"><span id="local-6989586621679171541"><span class="annot"><a href="#local-6989586621679171306"><span class="hs-identifier hs-type">node</span></a></span><span>
</span><span id="line-433"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Sized"><span class="hs-identifier hs-type">Sized</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171541"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-434"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171540"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171540"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171540"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171541"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171540"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171541"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171540"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-435"></span><span>    </span><span id="local-6989586621679171306"><span class="annot"><span class="annottext">node :: forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Node a -&gt; b
</span><a href="#local-6989586621679171306"><span class="hs-identifier hs-var hs-var">node</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Node a -&gt; b
forall a b.
Sized a =&gt;
(b -&gt; b -&gt; b) -&gt; (Int -&gt; a -&gt; b) -&gt; Int -&gt; Node a -&gt; b
</span><a href="Data.Sequence.Internal.html#foldWithIndexNode"><span class="hs-identifier hs-var">foldWithIndexNode</span></a></span><span>
</span><span id="line-436"></span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#foldToMaybeWithIndexTree"><span class="hs-pragma hs-type">foldToMaybeWithIndexTree</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-437"></span></pre></body></html>